但是存在一個(gè)特殊情況，如果操作的數(shù)組只存在兩個(gè)數(shù)據(jù)時(shí)，這種劃分方法就存在一些問(wèn)題，因?yàn)橐婚_(kāi)始兩個(gè)下標(biāo)i,j就指向了相同的位置，這時(shí)候如果a[0]大于a[1] ，那么經(jīng)過(guò)上面的操作以后j = 0, i = 1，這時(shí)候的pivot應(yīng)該是放在a[1]處，但是根據(jù)上面的條件可知，集合劃分至少需要三個(gè)元素，但是我們可以比較樞紐元與當(dāng)前a[j]的值，對(duì)于兩種情況下都滿足交換的條件就是a[j] < pivot,因此只要當(dāng)這個(gè)條件滿足是就交換a[j]和a[0]。上述的操作我們稱之為集合劃分操作。

int Partition(int *a, int left, int right)
{
/*采用第一個(gè)元素作為樞紐元*/
int pivot = a[left];
int i = left + 1;
int j = right;

/*只有一個(gè)元素，實(shí)際上不用進(jìn)行任何操作，直接返回*/
if(i > j)
return j;

/*實(shí)際上存在一個(gè)問(wèn)題就是i== j，這時(shí)候數(shù)組有兩個(gè)值*/
while(1)
{
/*跳過(guò)所有小于等于pivot的值，同時(shí)設(shè)置邊界條件*/
while(a[i] <= pivot && i < right)
++ i ;
/*跳過(guò)所有大于pivot的值，同時(shí)設(shè)置邊界條件*/
while(pivot < a[j] && j > left)
-- j ;
/*******************************************
*如果 i < j，則說(shuō)明數(shù)組之間存在間隔
*上面的條件全部不滿足則說(shuō)明找到S1，S2需要交換的數(shù)
*一般當(dāng)存在相同的數(shù)時(shí)，會(huì)存在i == j，這時(shí)實(shí)際上
*a[left] = a[j]
*一般都會(huì)產(chǎn)生i > j,這種情況發(fā)生在i+1=j時(shí)的交換操作
*交換操作完成以后i++,j--，使得i < j.
*******************************************/
if(i < j)
swap(&a[i ],&a[j]);
else
break;
}
/******************************************************
根據(jù)上面的分析實(shí)際上j下標(biāo)指向的數(shù)數(shù)都是小于或者等于pivot的
等于pivot時(shí)就不需要交換a[left]和a[j],只需要返回樞紐元應(yīng)該的位置即可，
同時(shí)也解決了只有兩個(gè)數(shù)值的數(shù)組問(wèn)題。
*******************************************************/
if(pivot > a[j])
swap(&a[left],&a[j]);
/*返回樞紐元應(yīng)該存在的位置*/
return j;
}

/*傳統(tǒng)的快速排序算法*/
void t_quickSort(int *a, int left, int right)
{
int i = 0;

/*如果left小于right*/
if(left < right)
{
/*找到樞紐元的位置，并劃分了兩個(gè)集合S1,S2*/
i = Partition(a,left,right);
/*S1集合排序*/
t_quickSort(a, left , i - 1);
/*S2集合排序*/
t_quickSort(a, i + 1, right);
}
}

但是這種方法存在一個(gè)比較嚴(yán)重的問(wèn)題，就是如果當(dāng)數(shù)組是一個(gè)已經(jīng)完成排序的情況，采用快速排序的時(shí)間復(fù)雜度將是災(zāi)難性的。此時(shí)的時(shí)間復(fù)雜度為O(N^2),也就是最壞的情況，為了解決這種問(wèn)題，采用了其他的解決方案，改變樞紐元的選擇決策，采用隨機(jī)選取或者三值的中值作為樞紐元。樞紐元的選擇能避免有序數(shù)組的快速排序問(wèn)題。還有就是當(dāng)數(shù)組的長(zhǎng)度較小時(shí)，采用插入法等常規(guī)方法的速度更快，而且如上面分析所示，劃分集合的問(wèn)題至少需要三個(gè)元素，雖然上面的方法能夠解決只有兩個(gè)元素的情況，但是如果考慮不周全就很難解決?？梢愿鶕?jù)長(zhǎng)度來(lái)選擇具體的排序排序方法，也就是當(dāng)長(zhǎng)度小于10時(shí)采用插入法排序，而當(dāng)大于10時(shí)就直接采用快速排序，這時(shí)候的注意事項(xiàng)就比較少，不用考慮數(shù)組長(zhǎng)度是否為2等。采用改良型的快速排序算法如下所示。

/*快速排序*/
void insertionSort(int *a, int left, int right)
{
int i = 0, j = 0;
int tmp = 0;
if(left >= right)
return;

for( i = left + 1; i <= right; ++ i)
{
tmp = a[i];
for(j = i; j > left && tmp < a[j - 1]; -- j)
a[j] = a[j - 1];
a[j] = tmp;
}
}

/*數(shù)據(jù)交換*/
void swap(int *a, int *b)
{
if(a != b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
}

/*選擇合適的樞紐元函數(shù)*/
int median(int *a, int left, int right)
{
int mid = (right + left) / 2;

if(a[mid] < a[left])
swap(&a[mid], &a[left]);
if(a[right] < a[left])
swap(&a[right], &a[left]);
if(a[right] < a[mid])
swap(&a[right], &a[mid]);

swap(&a[mid],&a[right - 1]);

return a[right - 1];
}

/*實(shí)現(xiàn)快速排序的實(shí)際函數(shù)*/
void quickSort(int *a, int left, int right)
{
int i = left, j = right - 1;
int pivot = 0;
if(left + 10 <= right)
{
/*選擇樞紐元*/
pivot = median(a,left,right);

while(1)
{
/*找到大于pivot的下標(biāo)*/
while(a[++ i] <= pivot){}
/*找到不大于pivot的下標(biāo)*/
while(a[--j] > pivot){}

if(i < j)
swap(&a[i],&a[j]);
else
break;
}
/*確定樞紐元的位置*/
swap(&a[i],&a[right - 1]);
quickSort(a,left,i - 1);
quickSort(a,i + 1,right);
}
else/*小長(zhǎng)度的數(shù)組采用插入法排序*/
insertionSort(a, left,right);
}

void QuickSort(int *a, int size)
{
quickSort(a,0,size - 1);
}

時(shí)間復(fù)雜度的測(cè)試，首先測(cè)試有序數(shù)組的排序操作，測(cè)試代碼和算法效果如下所示：

#define LEN 100000

int main()
{
int i = 0;
int a[LEN];
int b[LEN];
int c[LEN];
int d[LEN];
int e[LEN];
clock_t _start, _end;
double times = 0;

srand((int)time(0));

for(i = 0; i < LEN; ++ i)
{
a[i] = i;
b[i] = a[i];
c[i] = a[i];
d[i] = a[i];
e[i] = a[i];
}

_start = clock();
TQuickSort(a,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The QuickSort took %fs",times);
_start = clock();
QuickSort(b,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The Changed QuickSort took %fs",times);
#if 10
_start = clock();
MergeSort(c,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The MergeSort took %fs",times);

_start = clock();
InsertionSort(d,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The InsertionSort took %fs",times);

_start = clock();
heapSort(e,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The heapSort took %fs",times);
#endif
return 0;
}

結(jié)果如下：

[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 12.850000s
The Changed QuickSort took 0.000000s
The MergeSort took 0.030000s
The InsertionSort took 0.000000s
The heapSort took 0.020000s

從上面的實(shí)驗(yàn)結(jié)果可知，當(dāng)為有序數(shù)組時(shí)，快速排序的速度并不快，甚至是最慢的。插入排序反而是最快的方式。同時(shí)我們可以發(fā)現(xiàn)采用上面的改進(jìn)的快速排序算法排序速度很快，并不像傳統(tǒng)的算法那么費(fèi)時(shí)間。
測(cè)試采用隨機(jī)數(shù)產(chǎn)生的數(shù)組進(jìn)行排序時(shí)的實(shí)驗(yàn)效果：

[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 0.020000s
The Changed QuickSort took 0.010000s
The MergeSort took 0.030000s
The InsertionSort took 15.240000s
The heapSort took 0.020000s

從上面的結(jié)果可知，對(duì)于非有序的數(shù)組，快速排序的效果是非常好的，但是插入排序就非常的差勁啦。