前言
在理解了归并排序之后， 有一种更优秀的排序算法。上一次的简书中已经介绍了归并排序， 我们已经有了分治思想。快速排序在切分的时候不是采用对半分， 而是根据内容划分。思想是如果每一个元素在序列中， 左边序列元素 < 该元素 < 右边序列元素。 那么这个序列就是有序的序列。这就是基本思想。
主要解决的问题有两个
- 把一个序列按照一个算法， 使 左边序列元素 < 该元素 < 右边序列元素。
- 如何继续划分下去。
一、快速排序的切分(partition)
code
int partion(int *a, int lo, int hi){
int i = lo;
int j = hi + 1;
int v = a[lo];
while (true) {
while (a[++i] < v) if(i == hi) break;
while (v < a[--j]) if(j == lo) break;
if (i > j) break;
exc(a, i, j);
}
exc(a, lo, j);
return j;
}
代码会依靠切分值从两边向中扫描， 遇到不成有序的时候， 就停止， 交换他们。交换过后继续向中扫描， 直到 i > j停止。 此时已经两边有序， 交换切分值， 与最后的临界中点。 最后切分值， 左边的值都比它小， 而右边的切分值都比他大。返回新的j值， 作为下一次的切分点。
快速排序的切分
二、快速排序分治
上面已经有了单次的切分， 只要按照这样， 把序列分割切分部分有序下去， 就会有序了。当然递归方式很简单。
code
void quickSort(int *a, int lo, int hi){
if (hi <= lo) return;
int j = partion(a, lo, hi);
quickSort(a, lo, j - 1);
quickSort(a, j + 1, hi);
}
三、关于优化
小的范围插入排序表现更加优秀， 所以代码可以适当调节。
在重复元素较多的情况下， 切分任然过于繁琐， 可以采用三向切分的快速排序。
