目录
一、递归版本
1. hoare版本
（一）低配版
（二）高配版
①随机选key
②三数取中法选key（在begin，end，mid三个数中选）
2. 挖坑法
3. 前后指针版本（推荐，细节容易把控）
二、非递归版本
快速排序是Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。
区间按照基准值划分为左右两半部分的常见方式有：
一、递归版本
1. hoare版本
（一）低配版
什么是key？
key就是选出汗一个关键值key，把它放到正确的位置（最终排好序要去的位置）
第一轮排完之后，比6小的放左边，比6大的放右边
第一轮排序过程：
右边的R在找比key小的数 ， 左边的L在找比key大的数 ，找到了以后，交换这两个数（把小的往左边换，大的往右边换）
交换完之后R继续往左边走找比key小的数，L继续往右边走找比key大的数，找到之后交换这两个数，R再继续……直到L==R，相遇之后把key对应的数与L或R对应的数交换
注意一点：左边做key要让右边先走，反之亦然。
第一轮结束以后整个区间被分为三段，key的左边、key、key的右边
结束后key左边的值都比key小，右边的都比key大
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void QuickSort(int* a, int left,int right)
{//递归结束条件//当递归到begin==0，end==1，keyi==1时，区间通过[begin,kei-1] key [key+1,end]划分后//分为[0,0] keyi [2,1],此时会出现left>right的情况if (left >= right)return;int begin = left;int end = right;int keyi = left;while (left < right){//右边先走 找小while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的，这样的话right会飘出数组导致越界{--right;}//左边找大while (left < right&&a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;//[begin,kei-1] key [key+1,end]//递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, 9);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}
} 快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫 快速 排序
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(logN)
4. 稳定性：不稳定
影响快排性能的是key的位置，key的位置越接近中间就越能进行二分就越接近满二叉树
所以越有序反而快排效率越低
如何改进？
（二）高配版
①随机选key
int randi = left + (rand() % ( right - left));
Swap(& a[ left], & a[randi]);
int keyi = left;
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void QuickSort(int* a, int left,int right)
{//递归结束条件//当递归到begin==0，end==1，keyi==1时，区间通过[begin,kei-1] key [key+1,end]划分后//分为[0,0] keyi [2,1],此时会出现left>right的情况if (left >= right)return;int begin = left;int end = right;int randi = left + (rand() % (right - left));Swap(&a[left], &a[randi]);int keyi = left;while (left < right){//右边先走 找小while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的，这样的话right会飘出数组导致越界{--right;}//左边找大while (left < right&&a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;//[begin,kei-1] key [key+1,end]//递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, 9);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}
}
②三数取中法选key（在begin，end，mid三个数中选）
在有序或者接近有序的情况下选中间值效果最好
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;//求中间值if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])//此时mid最大{return left;}else{return right;}}else//a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值{return a[right];}else{return a[left];}}
}
void QuickSort(int* a, int left,int right)
{//递归结束条件//当递归到begin==0，end==1，keyi==1时，区间通过[begin,kei-1] key [key+1,end]划分后//分为[0,0] keyi [2,1],此时会出现left>right的情况if (left >= right)return;int begin = left;int end = right;//三数选中int mini = GetMidNumi(a, left, right);Swap(&a[left], &a[mini]);int keyi = left;while (left < right){//右边先走 找小while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的，这样的话right会飘出数组导致越界{--right;}//左边找大while (left < right&&a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;//[begin,kei-1] key [key+1,end]//递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, 9);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}
}为什么相遇的位置一定key小？
左边做key右边先走就能保证相遇位置一定比key小
相遇：
1、R找小，L找大没有找到，L遇到R，此时相遇位置比key小
2、R找小没有找到，直接跟L相遇，此时相遇位置比key小
类似道理，右边做key左边先走，相遇位置比key要大
2. 挖坑法
思路：
1、先将第一个数据存储在key中让第一个数据对应位置为空形成一个坑位
2、右边先走找比key小的位置后把那个比key小的数放到坑位里面去，此时右边形成了新的坑位
3、左边再走找比key大的数，找到后把这个数放到新的坑位里面去，此时又形成了新的坑位
4、以此类推，直到L和R相遇，一定相遇在坑里面，因为他们两一定有一个是坑，此时将key填到坑里面去排完后跟 hoare排完第一轮一般是不一样的
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void QuickSort(int* a, int left, int right)
{//递归结束条件//当递归到begin==0，end==1，keyi==1时，区间通过[begin,kei-1] key [key+1,end]划分后//分为[0,0] keyi [2,1],此时会出现left>right的情况if (left >= right)return;int begin = left;int end = right;//首先保存好值int key = a[left];//定义一个坑的位置int hole = left;while (left < right){//右边先走 找小while (left < right && a[right] >= key)//left<right,防止right在左边没有找到一个比key小的，这样的话right会飘出数组导致越界{--right;}a[hole] = a[right];hole = right;//左边找大while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;//[begin,hole-1] hole [hole+1,end]//递归QuickSort(a, begin, hole - 1);QuickSort(a, hole + 1, end);
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, 9);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}
}
3. 前后指针版本（推荐，细节容易把控）
1、cur找到比key小的值，++prev，cur和prev位置交换，++cur
2、cur找到比key大的值，++cur ( cur一直在找小 )
说明：
1、prev要么紧跟着cur（prev下一个就是cur）
2、prev跟cur中间间隔着比key大的一段区间
把比key大的值往右翻，比key小的值往左翻
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;//求中间值if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])//此时mid最大{return left;}else{return right;}}else//a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值{return a[right];}else{return a[left];}}
}
void QuickSort(int* a, int left, int right)
{//递归结束条件//当递归到begin==0，end==1，keyi==1时，区间通过[begin,kei-1] key [key+1,end]划分后//分为[0,0] keyi [2,1],此时会出现left>right的情况if (left >= right)return;int begin = left;int end = right;//三数选中int mini = GetMidNumi(a, left, right);Swap(&a[left], &a[mini]);int keyi = left;int prev = left;int cur = left + 1;while (cur<=right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;//[begin,kei-1] key [key+1,end]//递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, 9);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}
}二、非递归版本
递归改非递归：
1.直接改循环：斐波拉契
2.利用栈辅助改循环
之前递归的本质是区间的变化，那么栈也要存区间
#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else{return left;}}
}
void QuickSort(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);// 三数选中int mini = GetMidNumi(a, begin, end);// 修正：将 left 改为 beginSwap(&a[begin], &a[mini]);int keyi = begin;int prev = begin;int cur = begin + 1;// 修正：将 right 改为 endwhile (cur <= end){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;if (keyi + 1 < end){// 先入后出，先入右区间STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){// 先入后出，先入右区间STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, 9);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}return 0;
}