快速排序: 平均時間復(fù)雜度O(nlogn)，最壞時間復(fù)雜度O(n^2)，非穩(wěn)定排序
快速排序有兩個方向，左邊的i下標一直往右走，當(dāng)a[i] <= a[center_index]，其中center_index是中樞元素的數(shù)組下標，一般取為數(shù)組第0個元素。而右邊的j下標一直往左走，當(dāng)a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重復(fù)上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現(xiàn)在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻(這里所展示的是partition的第二種方案, partition2)。
partition1與partition2的優(yōu)劣具體參考《編程珠璣》 第11章
int
partition1(int *array, int begin, int end)
{
int pivot = array[begin];
int i, j = begin;
for(i=begin+1; i<=end; ++i) {
if(array[i] < pivot) {
++j;
if(i != j)
swap(array+i, array+j);
}
}
if(begin != j)
swap(array+begin, array+j);
return j;
}
int
partition2(int *array, int begin, int end)
{
int i, j, pivot = array[begin];
i = begin+1;
j = end;
while(1) {
while(i<=end && array[i]<pivot)
++i;
while(j>begin && array[j]>pivot)
--j;
if(i >= j)
break;
swap(array+i, array+j);
++i;
--j;
}
if(begin != j)
swap(array+begin, array+j);
return j;
}
void
quick_sort(int *array, int begin, int end)
{
if(begin >= end)
return;
int mid = partition2(array, begin, end);
quick_sort(array, begin, mid-1);
quick_sort(array, mid+1, end);
}