交换排序——快速排序

7.7 交换排序——快速排序

快速排序概念

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法（下文简称快排），其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左、右子序列分别重复该过程，直到所有元素都排列在相应位置上为止。

虽然快排是Hoare发明的，但Hoare并没有用自己的名字去给这个算法命名，而是用快速来对这个排序命名，用于彰显这个排序算法的特点：快。

例如我们设基准值为div，则排序的目的是为了完成这个目标：

这个是二叉树结构的交换排序，所以div左边和div右边的区间还要分别重复这个过程。

c语言的库函数qsort

c语言中就有一个库函数qsort：

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

它的4个参数表示的含义：

• base：被用来排序的数组的数组名或数组的首元素地址。
• num：数组的元素个数。
• width：数组的单个元素占用的内存大小。
• compare：程序员自定义的比较函数。

用户自定义的比较函数需要返回两个元素之间的差值。这很大程度上局限了这个函数的玩法（比如实现自定义类型数组的排序可能会比较麻烦）。但这个函数的底层实现就是快速排序，比一般的排序算法的速度要快。

应用实例：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdlib.h>
#include<stdbool.h>typedef int Datatype;//用户自定义的比较函数
int cmp(const void* a, const void* b) {//升序排序return (*(Datatype*)a) - (*(Datatype*)b);//这个函数通过差值判断是否交换
}void f() {srand((size_t)time(0));//随机数的种子Datatype a[30] = { 0 };int i = 0;for (i = 0; i < 30; i++) {a[i] = rand() % 100 + 1;//生成随机数printf("%d ", a[i]);}printf("\n");//四个形参分别是数组名，要排序的元素个数，单个元素的大小，程序员自定义的比较函数qsort(a, sizeof(a)/sizeof(a[0]), sizeof(Datatype), cmp);for (i = 0; i < 30; i++)printf("%d ", a[i]);
}int main() {f();return 0;
}

快速排序框架quickSort

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void quickSort(Datatype* array, int left, int right)
{if (right - left <= 0)//区间只有1个值或区间不存在时没必要继续分return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int keyi = partSort(array, left, right);// 划分成功后以keyi为边界形成了左右两部分 [left, keyi) 和 [keyi+1, right)// 递归排[left, div)quickSort(array, left, keyi - 1);// 递归排[div+1, right)quickSort(array, keyi + 1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，我们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

虽然快速排序性能很优异，但并不是所有情况快排都是最优选。甚至数据量小的情况比如10个数据，快排对这10个数据排序，耗时说不定比插入排序慢。我们学习排序是为了能判断所有情况，并根据情况选择合适的排序算法来处理数据。

10个数据组成的数组看成完全二叉树就是4层，递归的话还要多调用3次函数，每次调用函数都要向内存申请空间，加大时间和空间的成本。

若使用插入排序来处理这种数量比较小的数据，则减少了多余的递归调用。能使排序完成时间缩短。

以满二叉树为例子，最底层占$50\%$的结点，后层数网上逐级减半，3层的优化效率就是

$50\%+25\%+12.5\%=87.5\%$。

虽然我们不知道这个优化效率是怎么算出来的，但是我们可以通过高精度计时库来计算10个元素时两种排序的耗时。参考程序如下（c++程序）：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdlib.h>
#include<stdbool.h>
#include<chrono>
#include<iostream>
using namespace std;typedef int Datatype;int cmp(const void* a, const void* b) {return (*(Datatype*)a) - (*(Datatype*)b);
}void insertSort(Datatype* a, int n) {int i = 0;for (i = 0; i < n - 1; i++) {int end = i;int tmp = a[i + 1];while (end >= 0)if (a[end] > tmp) {a[end + 1] = a[end];--end;}else break;a[end + 1] = tmp;}
}void f() {srand((size_t)time(0));Datatype a[10], b[10];int i = 0;for (i = 0; i < 10; i++) {a[i] = rand() % 1000 + 1;b[i] = a[i];}auto begin = std::chrono::high_resolution_clock::now();qsort(a, 10, 4, cmp);//用快排对10个数据进行排序auto end = std::chrono::high_resolution_clock::now();std::chrono::duration<double> time1 = end - begin;std::cout << time1.count() << endl;auto begin2 = std::chrono::high_resolution_clock::now();insertSort(b, 10);//用插入排序对10个数据进行排序auto end2 = std::chrono::high_resolution_clock::now();std::chrono::duration<double> time2 = end2 - begin2;std::cout << time2.count() << endl;//如果快排用时比插入排序用时长，则输出1，否则输出0cout << (time1.count() - time2.count() > 1e-15) << endl;
}int main() {f();return 0;
}

chrono 库的 high_resolution_clock 可以提供高精度的时间点，通过计算两个时间点的差值来得到代码执行的时间间隔， duration<double> 用于以秒为单位表示时间间隔， count() 函数返回该时间间隔的值。

用大量数据时表现不好，小量数据时表现优异的算法处理这种小规模数据的优化方式，有人称作小区间优化。这种优化的本质是一种锦上添花的行为，无法改变算法本身的弊端。

到这里为冒泡排序惋惜1秒钟，我确实没遇到过最适合冒泡排序的应用场景。

关于partSort函数的实现，因为内容太多，分成几篇来写。