快速排序是交换排序的一种，算法效率高，需要额外的辅助空间
1. 算法思想
从待排序序列中选取一个元素，以其值作为中间值，把比其小的元素放到左边，比起大的元素放到右边；然后递归地对左、右部分排序，直至每一部分元素个数为1，整个序列有序。
2. 时间复杂度
用递归树的思想，每次划分操作的元素总数都是n，因此每次划分的时间复杂度都是O(n)，接下来只需考虑划分次数：
最好情况 O(nlogn)：每次都将序列等分为两部分，因此划分次数为logn
最坏情况 O(n^2)：每次都有一部分只分出一个元素，因此划分次数为n
3. 空间复杂度 O(logn)
递归调用，考虑递归栈的空间消耗
4. 稳定性
不稳定。划分时要跨中轴交换元素，不相邻交换不稳定
5. 代码实现（C语言）
划分时有两类方法：
一种是挖坑法，将A[0]作为中轴值保存到value中，A[0]空出一个坑；先从后往前遍历，遇到不大于value的数A[j]，则将A[j]填到A[0]中，A[j]空出一个坑；再从前往后遍历，遇到不小于value的数A[i]，则将A[i]填到A[j]中，A[i]空出一个坑。如此循环，直至i、j重合，将value填到这个坑中。
另一种是交换法，同时从后往前找小于value的A[j]，从前往后找不小于value的A[i]，然后交换A[i]、A[j]；循环直至i、j重合。这种方法在保证重合处的值A[i]小于value，因此递归划分时前半部分要包括A[i]。但是将等于value的值都放到后半部分了，对于有大量相同元素的序列，会因为划分不均匀而导致效率偏低，因此整体看来稍逊一筹。
为了使中轴值取得更有效，这里采用取序列首、尾、中间元素的中值的方法，代码如下：
int Adjust(int *A, int low, int high){ int ind; int mid = (low + high) / 2; int value = A[low]; if (A[low] <= A[mid]) { ind = A[mid] <= A[high] ? mid : (A[low] <= A[high] ? high : low); } else { ind = A[low] <= A[high] ? mid : (A[mid] <= A[high] ? high : mid); } if (ind != low) { value = A[ind]; A[ind] = A[low]; A[low] = value; } return value;} 另外为了接口一致，增加了一个入口函数：void QuickSort(int *A, int n){ QSort(A, 0, n - 1);}接下来是快排函数，首先是挖坑版：
void QSort(int *A, int low, int high){ int i, j, value; if (low >= high) { return; } i = low; j = high; value = Adjust(A, low, high); while(i < j) { while (i < j && A[j] > value) { --j; } if (i < j) { A[i++] = A[j]; } while (i < j && A[i] < value) { ++i; } if (i < j) { A[j--] = A[i]; } } A[i] = value; QSort(A, low, i - 1); QSort(A, i + 1, high);} 再看一下交换版：void QSort(int *A, int low, int high){ int i, j; int tmp, value; if (low >= high) { return; } i = low; j = high; value = Adjust(A, low, high); while (i < j) { while (i < j && A[j] >= value) { --j; } while (i < j && A[i] < value) { ++i; } if (i < j) { tmp = A[i]; A[i] = A[j]; A[j] = tmp; } } QSort(A, low, i); QSort(A, i + 1, high);}版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
