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

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

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

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

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

/*實現(xiàn)快速排序的實際函數(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的下標*/
while(a[++ i] <= pivot){}
/*找到不大于pivot的下標*/
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/*小長度的數(shù)組采用插入法排序*/
insertionSort(a, left,right);
}

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

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

#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

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

[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é)果可知，對于非有序的數(shù)組，快速排序的效果是非常好的，但是插入排序就非常的差勁啦。