快排（六大排序）

快速排序

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

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，

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

此动图演示的为hoare的版本标记点在最右侧为P，因此需要让左面的L先走

在代码实现中，我们将左侧为标记P，所以让右侧先走

将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本

2. 挖坑法

3. 前后指针版本(用指针cur和prev裹挟着比key大的值向后移动)

快速排序优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序

代码实现：

// 时间复杂度：O(N*logN)   
// 什么情况快排最坏：有序/接近有序 ->O(N^2)
// 但是如果加上随机选key或者三数取中选key，最坏情况不会出现，所以这里不看最坏
// 小区间优化
// 面试让你手撕快排，不要管三数取中和小区间优化
// Hoare
void QuickSort(int* a, int left, int right)
{if (left >= right)return;//小区间优化if (right - left + 1 < 10){//是a+leftInsertSort(a+left, right - left + 1);}else{// 100 200，注意的是left不一定是0// 选[left, right]区间中的随机数做key//int randi = rand() % (right - left + 1);//randi += left;//Swap(&a[left], &a[randi]);int mid = MidIndex(a, left, right);//交换Swap( &a[left], &a[mid]);int keyi = left;int begin = left;int end = right;while (left < right){//右面先走,找比key小的值，确保最后值比key小while (left < right && a[right] >= a[keyi]){--right;}while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[right]);//千万别忘了keyi = right;//[begin  keyi-1] keyi [keyi+1    end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}void QuickSort2(int* a, int left, int right)
{if (left >= right)return;//小区间优化if (right - left + 1 < 10){//是a+leftInsertSort(a + left, right - left + 1);}else{int mid = MidIndex(a, left, right);//交换Swap(&a[mid], &a[left]);int keyi = left;//prev curint cur = left + 1;int prev = left;while (cur <= right){if (a[cur] < a[keyi]){++prev;Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;//[left  keyi-1] keyi [keyi+1    right]QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi + 1, right);}
}#include"Stack.h"
void QuickSortNor(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 keyi = begin;int cur = begin + 1;int prev = begin;while (cur <= end){if (a[cur] < a[keyi]){++prev;Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;//是begin不是0//[begin  keyi-1] keyi [keyi+1  end]  先入右面，再入左面if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}