一，快速排序（递归）
1，快排思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止；
基本代码思想如下：
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right < left) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div+1, right) QuickSort(array, div+1, right); }
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可；
2，霍尔排序
根据快排思想，我们需要实现的就是 partion 函数了----将区间按照基准值划分为左右两半部分；
常见的方式有很多，我们先来了解最初的版本 【霍尔排序】
思想图解：
对就是这样的，右边的小人先出发向左移动，找到比 key 小的数，然后左边的小人向右移动找到比 key 大的数，然后交换两个小人的值，直至他们相遇然后再交换 key 与任意一个小人的值；
这样一趟下来，他们相遇后，左边的数都比 key 小，右边的数都比 key 大；
思路实现：
//霍尔排序 int PartSort1(int* arr, int left, int right) { int keyi = left; while (left < right) { //右边先走 while (left<right && arr[right]>=arr[keyi]) { right--; } //左边后走 while (left < right && arr[left] <= arr[keyi]) { left++; } //交换 Swap(&arr[left], &arr[right]); } Swap(&arr[left], &arr[keyi]); return left; }
然后我们运行一下：
//快速排序 void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return NULL; } //霍尔法 int keyi = PartSort1(arr, begin, end); //排序[begin,keyi) & [keyi+1,end] QuickSort(arr, begin, keyi); QuickSort(arr, keyi + 1, end); } int main() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; //快速排序 QuickSort(arr, 0,sizeof(arr) / sizeof(arr[0])-1); PrintSort(arr, sizeof(arr) / sizeof(arr[0])); return 0; }
可以看到是有序的，选择排序就 OK 了；
3，挖坑法
然后我们再来认识另一种方式 【挖坑法】，其实跟【霍尔排序】思路差不多，不过更容易理解一点；
思想图解:
对还是一样的思路，让第一个元素为坑位，然后右边的小人先出发向左走找比 key 小的数，然后填充坑位并且右边小人的位置变为新坑位，然后左边的小人向右走找比 key 大的数，然后填充坑位并且左边小人的位置变为新坑位，直至两个小人相遇于坑位然后再给坑位赋值 key ；
这样一趟下来，坑位左边的数都比 key 小，右边的数都比 key 大；
思路实现：
//挖坑法 int PartSort2(int* arr, int left, int right) { int key = arr[left]; //坑位 int hole = left; while (left < right) { //右边找小 while (left < right && arr[right] >= key) { right--; } arr[hole] = arr[right]; hole = right; //左边找大 while (left < right && arr[left] <= key) { left++; } arr[hole] = arr[left]; hole = left; } arr[hole] = key; return hole; }
然后我们运行一下：
//快速排序 void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return NULL; } //挖坑法 int keyi = PartSort2(arr, begin, end); //排序[begin,keyi) & [keyi+1,end] QuickSort(arr, begin, keyi); QuickSort(arr, keyi + 1, end); }
可以看到是有序的，选择排序就 OK 了；
4，前后指针法
然后呢，在介绍最后一种排序方式了 【前后指针】法；
这个呢就比较新颖了，跟之前的都不一样；
请看图解：
这个呢就是，定义两个指针，从首元素开始走，快指针（cur）刚开始领先慢指针（prev）一个身位，然后 cur 先走找比 key 小的数，然后与 prev 的下一个数交换，直至 cur 越界，然后再让 prev 与 key 交换；
这样一趟下来，prev左边的数都比 key 小，右边的数都比 key 大；
思路实现：
//前后指针法 int PartSort3(int* arr, int left, int right) { int keyi = left; int slow = left, fast = left+1; while (fast<=right) { if (arr[fast] < arr[keyi] && ++slow!=fast) { //交换 Swap(&arr[fast], &arr[slow]); } fast++; } Swap(&arr[slow], &arr[keyi]); return slow; }
然后我们运行一下：
//快速排序 void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return NULL; } int keyi = PartSort3(arr, begin, end); //排序[begin,keyi) & [keyi+1,end] QuickSort(arr, begin, keyi); QuickSort(arr, keyi + 1, end); }
可以看到是有序的，选择排序就 OK 了；
5，快速排序优化
1，三数取中法选key
这第一个呢，就是对 key 的取值进行优化，当 key 的值太过于小或者大时，遍历数组的时间会增加，所以我们尽量让 key 的取值随机；
我们可以取首元素，尾元素，中间元素的值进行比较选 key ；
思路实现：
//三数取中 int middle(int* arr, int left, int right) { //int mid = (left +right)/ 2; if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) { return mid; } if (arr[left] < arr[right]) { return right; } else { return left; } } //arr[mid]<=arr[left] else { if (arr[mid] > arr[right]) { return mid; } if (arr[left] > arr[right]) { return right; } else { return left; } } }
这样我们选择的 key 就不会受 首元素的束缚了；
我们还可不可以在这个基础上再优化一下呢？
答案是肯定的！
我们可以用随机数来取代中间数；
//三数取中 int middle(int* arr, int left, int right) { //随机数取中 int mid = left + (rand() % (right - left)); if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) { return mid; } if (arr[left] < arr[right]) { return right; } else { return left; } } //arr[mid]<=arr[left] else { if (arr[mid] > arr[right]) { return mid; } if (arr[left] > arr[right]) { return right; } else { return left; } } }
这样子才是真正意义上的随机值，这样 key 就不受束缚了，再任何场景下都可以排序自如；
我们选完 key 的下标后，要让数组首元素的值与之交换，这样后面不动就 OK 了；
以【前后指针法】为例：
//前后指针法 int PartSort3(int* arr, int left, int right) { //三数取中 int ret = middle(arr, left, right); Swap(&arr[left], &arr[ret]); int keyi = left; int slow = left, fast = left+1; while (fast<=right) { if (arr[fast] < arr[keyi] && ++slow!=fast) { //交换 Swap(&arr[fast], &arr[slow]); } fast++; } Swap(&arr[slow], &arr[keyi]); return slow; }
主函数需要写 srand 函数来引用随机值；
//快速排序 void QuickSort(int* arr, int begin, int end) { srand(time(0)); if (begin >= end) { return NULL; } int keyi = PartSort3(arr, begin, end); //排序[begin,keyi) & [keyi+1,end] QuickSort(arr, begin, keyi); QuickSort(arr, keyi + 1, end); }
现在我们运行测试一下：
其实速度是更快的，大家可以在【力扣】上测试一下；
2，小区间优化
还有一种优化方式是当递归到小的子区间时，可以考虑使用插入排序；
当数组的区间不大时，使用【插入排序】是会更快的，同时也可以减少压栈的次数，也就是降低【空间复杂度】；
//快速排序 void QuickSort(int* arr, int begin, int end) { srand(time(0)); if (begin >= end) { return NULL; } if (end - begin <10) { InsertSort1(arr,begin,end); } else { int keyi = PartSort3(arr, begin, end); //排序[begin,keyi) & [keyi+1,end] QuickSort(arr, begin, keyi); QuickSort(arr, keyi + 1, end); } }
然后我们还需要改变一下插入排序，之前都是传数组元素个数的，现在我们要传区间需要改造一下；
//插入排序(改造版) void InsertSort1(int* arr, int left, int right) { int i = 0; for (i = left; i < right; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] >= tmp) { //交换 Swap(&arr[end], &arr[end + 1]); end--; } else { break; } } arr[end + 1] = tmp; } }
这样就可以了，现在我们运行测试一下：
可以看到是有序的，选择排序就 OK 了；
二，快速排序（非递归）
之前咱们拿捏了递归版的快速排序，现在咱们来秒杀非递归版的快速排序；
我们之前了解到，快速排序与二叉树的前序遍历相似，所以我们非递归也要用这种手法来表示；
所以我们需要借助【栈】来帮助我们来实现；
因为【栈】的特性（后进先出）很符合二叉树的前序遍历的思想，这样我们可以先排序最左边的序列，在排序右边的，前面的都放在【栈】】里等后面排序；
所以我们需要一个【栈】：
Stack.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct StackTop { STDataType* a; int top; int capacity; }ST; //初始化 void STInit(ST* ps); //销毁 void STDestroy(ST* ps); //插入 void STPush(ST* ps, STDataType x); //删除 void STPop(ST* ps); //返回栈顶 STDataType STInsert(ST* ps); //数量 int STSize(ST* ps); //判断是否为空 int STEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" //初始化 void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; } //销毁 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //插入 void STPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { ps->capacity = ps->top == 0 ? 4 : ps->capacity*2; ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity); } ps->a[ps->top] = x; ps->top++; } //删除 void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } //返回栈顶 STDataType STInsert(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top-1]; } //数量 int STSize(ST* ps) { assert(ps); return ps->top; } //判断是否为空 int STEmpty(ST* ps) { assert(ps); if (ps->top == 0) { return 1; } else { return 0; } }
然后我们就可以实现代码了；
我们的思路是：
将两边的下标存进【栈】，然后再取栈顶元素进行排序（霍尔或者其他），每取一个栈顶元素之后要把栈顶元素删除，然后再存放 keyi 两边的区间，再重复上面的过程，直至【栈】为空排序结束；
//快速排序(非递归) void QuickNon(int* arr, int begin, int end) { srand(time(0)); ST ps; //初始化 STInit(&ps); if (begin >= end) { return; } //插入 STPush(&ps, end); STPush(&ps, begin); //栈不为空就进去 while (!STEmpty(&ps)) { int left = STInsert(&ps);//栈顶元素 STPop(&ps);//删除 int right = STInsert(&ps); STPop(&ps); int keyi = PartSort1(arr, left, right); //排序[left,keyi-1] & [keyi+1,right] if (keyi + 1 < right) { //插入 STPush(&ps, right); STPush(&ps, keyi + 1); } if (left < keyi - 1) { //插入 STPush(&ps, keyi - 1); STPush(&ps, left); } } //销毁 STDestroy(&ps); }
我们运行测试一下：
可以看到也是完全 OK 的；
这就是快速排序的非递归实现！
三，快速排序源代码
以上的快速排序的全部代码如下（不包括【栈】）：
//三数取中 int middle(int* arr, int left, int right) { //int mid = (left +right)/ 2; //随机数取中 int mid = left + (rand() % (right - left)); if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) { return mid; } if (arr[left] < arr[right]) { return right; } else { return left; } } //arr[mid]<=arr[left] else { if (arr[mid] > arr[right]) { return mid; } if (arr[left] > arr[right]) { return right; } else { return left; } } } //霍尔排序 int PartSort1(int* arr, int left, int right) { //三数取中 int ret = middle(arr, left, right); Swap(&arr[left], &arr[ret]); int keyi = left; while (left < right) { //右边先走 while (left<right && arr[right]>=arr[keyi]) { right--; } //左边后走 while (left < right && arr[left] <= arr[keyi]) { left++; } //交换 Swap(&arr[left], &arr[right]); } Swap(&arr[left], &arr[keyi]); return left; } //挖坑法 int PartSort2(int* arr, int left, int right) { //三数取中 int ret = middle(arr, left, right); Swap(&arr[left], &arr[ret]); int key = arr[left]; int hole = left; while (left < right) { while (left < right && arr[right] >= key) { right--; } arr[hole] = arr[right]; hole = right; while (left < right && arr[left] <= key) { left++; } arr[hole] = arr[left]; hole = left; } arr[hole] = key; return hole; } //前后指针法 int PartSort3(int* arr, int left, int right) { //三数取中 int ret = middle(arr, left, right); Swap(&arr[left], &arr[ret]); int keyi = left; int slow = left, fast = left+1; while (fast<=right) { if (arr[fast] < arr[keyi] && ++slow!=fast) { //交换 Swap(&arr[fast], &arr[slow]); } fast++; } Swap(&arr[slow], &arr[keyi]); return slow; } //插入排序(改造版) void InsertSort1(int* arr, int left, int right) { int i = 0; for (i = left; i < right; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] >= tmp) { //交换 Swap(&arr[end], &arr[end + 1]); end--; } else { break; } } arr[end + 1] = tmp; } } //快速排序 void QuickSort(int* arr, int begin, int end) { srand(time(0)); if (begin >= end) { return NULL; } if (end - begin <10) { InsertSort1(arr,begin,end); } else { int keyi = PartSort1(arr, begin, end); //排序[begin,keyi) & [keyi+1,end] QuickSort(arr, begin, keyi); QuickSort(arr, keyi + 1, end); } } //快速排序(非递归) void QuickNon(int* arr, int begin, int end) { srand(time(0)); ST ps; //初始化 STInit(&ps); if (begin >= end) { return; } //插入 STPush(&ps, end); STPush(&ps, begin); //栈不为空就进去 while (!STEmpty(&ps)) { int left = STInsert(&ps);//栈顶元素 STPop(&ps);//删除 int right = STInsert(&ps); STPop(&ps); int keyi = PartSort1(arr, left, right); //排序[left,keyi-1] & [keyi+1,right] if (keyi + 1 < right) { //插入 STPush(&ps, right); STPush(&ps, keyi + 1); } if (left < keyi - 1) { //插入 STPush(&ps, keyi - 1); STPush(&ps, left); } } //销毁 STDestroy(&ps); }
特性总结：
1，快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2.，时间复杂度：O(N*logN)
3.，空间复杂
度：O(logN)
4， 稳定性：不稳定
第三阶段就到这里了，带大家啃块硬骨头磨磨牙！
后面博主会陆续更新；
如有不足之处欢迎来补充交流！
完结。。
