快速排序

快速排序也是基于分治的思想，通过选择分割基准（分割基准可以取第一个元素，最后一个元素，中间元素，也可以随机的方式选取一个元素），将小于等于中间值的都放在左边，大于中间值的都放在右边，将数组分割为前后两个局部数组，然后对前后两个局部数组，通过递归调用进行分割，将数组分割为越来越小的子数组，在每一步的调用中，经过多次的交换，最终为中心元素找到最终位置，从而完成给定数组的排序。
可以看到快速排序的核心是分割，那么我们就先通过一个例子说明如何分割。
现在我们需要对数组 {3,9,8,1,5,6,2,5} 进行分割，数组的分割对象为 p 到 r （包含p和r）, 这里选择分割的基准为 x（即A[r]）。接下来对A中的元素进行移动，将小于等于 A[r] 的元素移动到 p 到 i 的范围（包含i）, 将大于 A[r] 的元素移动到 i+1到 j (不包含 j )的范围内，最后将 A[i+1] 与 A[r] 交换。其中 i 初始化为 p-1, j 初始化为 p。

分割所用的下标.png
j 每经过依次循环就向后移动一个位置，从而将A[j]归入正确的组内，共有两种情况：
1）A[j] 大于 x 时不移动元素，直接将 j 向后移动一个位置，将 A[j] 归入“大于x的组”；
2）A[j] 小于等于 x，先让 i 向后移动一个位置，然后交换 A[i] 与 A[j],这样 A[j] 就进入了”小于等于 x 的组”，同时随着 j 向后移动一个位置，原本位于 A[i] 的元素又会回到“大于x的数组”。
最后将 A[i+1] 与 A[r] 交换，完成分割。
分割示例.jpg
接下来我们贴出代码：
<pre>
//分割
int partition(int A[], int n, int p, int r){
int i, j;
int t, x;
x = A[r];
i = p - 1;
for (j = p; j < r;j++){
if (A[j] <= x){
i++;
t = A[i]; A[i] = A[j]; A[j] = t;
}
}
t = A[i + 1]; A[i + 1] = A[r]; A[r] = t;
trace(A, n);
return i + 1;
};
//快速排序
void quickSort(int A[], int n, int p, int r){
int q;
if (p < r){
q = partition(A,n,p,r);
quickSort(A,n,p,q-1);
quickSort(A,n,q+1,r);
}
}
</pre>
结果：
下图是对数组进行快速排序的过程，便于和程序运行结果相对比。
快速排序步骤.jpg
运行结果.png
稳定性：快速排序在分割的过程中会交换不相邻的元素，因此属于不稳定的排序算法。
复杂度：如果快速排序在分割时能恰好选择中间值，则整个过程与归并排序一样大致分为 log2(n) 层，快速排序的平均复杂度为 O(nlogn)。
总结：快速排序与归并排序一样基于分治法，但其执行分割时就已经在原数组中完成了排序，因此不需要归并排序中的手动合并处理。此外归并排序需要O(n)的外部存储空间，快速排序则不需要额外的内存，是一种原地排序（内部排序）。在本例中我们选用的基准是 A[r], 因此在处理某些顺序的数据（例如一排序完毕的数据）时效率会大打折扣，最坏情况下复杂度甚至高达O(n2), 此外某些顺序的数据可能让递归深度过深，最终导致栈溢出，一般情况下，需要在基准的选择上多花些心思，比如随机选择，或者任选几个值后取中间值等。
至此，几种常见的排序方法都已经理解了，第一次静下心来理了理这几种算法，以上的理解大都源自下面这本书，讲得特别详细，对算法的讲解大部分有应用实例和框图解释，所以很容易理解，值得好好看一下！
挑战程序设计竞赛.png