快速排序: 平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)，非稳定排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻(这里所展示的是partition的第二种方案, partition2)。
partition1与partition2的优劣具体参考《编程珠玑》 第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);
}