交换排序——快速排序
- 7.7 交换排序——快速排序
- 快速排序概念
- c语言的库函数qsort
- 快速排序框架quickSort
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 % 50\% 50%的结点，后层数网上逐级减半，3层的优化效率就是
50 % + 25 % + 12.5 % = 87.5 % 50\%+25\%+12.5\%=87.5\% 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，否则输出0 cout << (time1.count() - time2.count() > 1e-15) << endl; } int main() { f(); return 0; }
chrono库的high_resolution_clock可以提供高精度的时间点，通过计算两个时间点的差值来得到代码执行的时间间隔，duration<double>用于以秒为单位表示时间间隔，count()函数返回该时间间隔的值。用大量数据时表现不好，小量数据时表现优异的算法处理这种小规模数据的优化方式，有人称作小区间优化。这种优化的本质是一种锦上添花的行为，无法改变算法本身的弊端。
到这里为冒泡排序惋惜1秒钟，我确实没遇到过最适合冒泡排序的应用场景。
关于partSort函数的实现，因为内容太多，分成几篇来写。
