分治算法之快速排序
算法简介
快速排序（Quick Sort）又称分化交换排序，是冒泡排序的一种改进。著名的计算机科学家霍尔（C.A.Hore）给出的快速分类算法也是根据分治策略中的一种高效率的分类算法。在快速排序中，记录的比较和交换是从两端向中间进行的，关键字值较大的记录一次就能交换到后面单元，关键字值较小的的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。快速排序是基于分治册罗的另一个排序算法。
算法思想
快速排序的思想是基于分治思想。假设给出了一组待排序的数字,假设区间是从l-r,如下图所示
?
算法的步骤如下
-
首先是确定分界点。分界点可以在区间内任意选取，一般取的是q[l],q[l+r/2],q[r]，注意这里取得是待排序中的数字。
-
确定好分界点之后 ，通过x的值划分成两个部分，这两个部分的的长度不一定相等，使得第一个区间里的数都小于等于x，第二个区间里的数都大于等于x。
-
递归处理左右两段。
注意
在第二步中是难点，解决的办法有很多。可以通过暴力算法解决：
-
首先开辟两个数组a[],b[].
-
扫描待排序的数组中的没一个数。如果扫描的数字小于x,则将其放到a数组中，否则放到b数组中。
-
然后依次将a，b数组中的数放到q数组中。
也可以通过很优美的算法解决（通过指针的方法解决）：
通过两个指针i,j分别指向待排序数组的左右两边l,r,两个指针同时向中间移动。i指针指向的数字如果要小于x的话就继续v往后移动，直到移动到的数字大于x的值就停下来。同样j指针也是如此，走到小于x的数字就停下来。此时两个指针指向的数都需要进行交换，把两个指针指向的数字进行交换。交换之后，i指针指向的数都小于等于x，j指针指向的数都大于等于x。直到i和j相遇或者穿过，此时两个区间就已经划分好了。
算法案例模拟
给定你一个长度为n的整数数列。请你用快速排序对这个数列按照从小到打进行排序。并将排序好的数列按照顺序输出。
#include<iostream>
using namespace std;
?
const int N = 1e6 + 10;
?
int n;
int q[N];
?
void quick_sort(int q[], int l, int r){
if (l >= r) return;
int x = q[l], i = l - 1, j = r + 1;
while (i < j){
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
?
int main(){
scanf_s("%d", &n);
for (int i = 0; i < n; i++){
scanf_s("%d", &q[i]);
}
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i++){
printf("%d ", q[i]);
}
system("pause");
}
代码运行截图：
?
边界问题
在quick_sort(q,l,j) quick_sort(q,j+1,r)中，其中r也可以写成quick_sort(q,l,i-1) quick_sort(q,i,r).但是此时在划分边界的时候x不能取到左边界（即x=q[l]）,可以取成x=q[(l+r+1)/2]或者x=q[r].因为如果当x=q[l]时，quick_sort(q,l,i-1) quick_sort(q,i,r)时会出现死循环，如下图:
?