快速排序

①hoare版本

思路分析

以上图为例：
指定一个数为a[key] = 6，a[right] 从尾出发找比 6 小的数，找到后停下，接着a[left] 从头出发找比 6 大的数，找到后停下 → Swap(&a[left], &a[right]) ，最终 a[right] 和 a[left] 相遇 → Swap(&a[key], &a[right]);//left==right

• 这样就分割出了左右区间，左区间的数都比 6 小，右区间的数都比 6 大
• 6 已经落到正确的位置
• 解下来就是以左右区间为新数列，重复上述操作
  
  Swap(&a[key], &a[right]);//left==right 分析：

1. right 停住，left 往后走 与 right 相遇 ⇨ 相遇的位置是right 停住的位置 👉 right 找到要找的数才会停下（始终在 left < right 的约束下），此时相遇点就是 right 找到的比 a[key] 小的数
2. left 停住，right 往前走 与 left 相遇 ⇨ 相遇的位置是 left 停住的位置 👉 right 比 left 先走，right 找到了 ，left 才会动，left停住之后，则会Swap(&a[left], &a[right]) ，Swap 之后此时a[left] < a[key] ，left 停住，right 往前走（如果一直未找到要找的数）与 left 相遇，此时相遇点就是比 a[key] 小的数

⭐左边做 key，右边先走；
⭐右边做 key，左边先走；

• 一些bug代码分析：

while (left < right)
{while (a[right] > a[key]){--right;}while (a[left] < a[key]){++left;}Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[right]);//left==right

3. 相等的情况：

Swap之后：

这样循环就会卡住 👇

while (left < right)
{while (a[right] > a[key]){}//循环不进入while (a[left] < a[key]){}//循环不进入Swap(&a[left], &a[right]);//一直无限循环Swap
}

4. 越界

while (left < right)
{while (a[right] >= a[key]){--right;}while (a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);
}

right 飞出去的情况：

left 飞出去的情况：

因此，right 和 left 每次改变之后都需要判断是否 left < right

代码实现

int hoareSort1(int* a, int left, int right)
{assert(a);if (left >= right)return;int key = left, begin = left, end = right;while (left < right){while (left < right && a[right] >= a[key]){--right;}while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[key], &a[right]);//left==right//[begin,left-1] [right+1,end]hoareSort1(a, begin, left - 1);hoareSort1(a, right + 1, end);return right;
}

时间复杂度

• 最好的情况（像二叉树一样）：如下图 时间复杂度为O(N*logN)
  
• 比较一般的情况：
  
• 最坏的情况：有序
  
  Σ = n + (n-1) + (n-2) + …… + 2 + 1 = (n+1)*n/2
  ∴ 时间复杂度为 O(N²)

<整体优化>

• 三数取中（begin、middle、end）
  • 例如：

∵ 1 < 6 < 9
∴ 选择 a[middle] 作为 a[key]

// 三数取中
int GetMidIndex(int* a, int left, int right)
{int begin = left, end = right;int middle = (left + right) / 2;if (a[begin] < a[end]){if (a[middle] < a[begin])return begin;else if (a[middle] > a[end])return end;elsereturn middle;}else{if (a[middle] < a[end])return end;else if (a[middle] > a[begin])return begin;elsereturn middle;}}
// 快速排序hoare版本
int hoareSort1(int* a, int left, int right)
{assert(a);if (left >= right)return;int key = left, begin = left, end = right;int mid = GetMidIndex(a, left, right);Swap(&a[mid], &a[key]);while (left < right){while (left < right && a[right] >= a[key]){--right;}while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[key], &a[right]);//left==right//[begin,left-1] [right+1,end]hoareSort1(a, begin, left - 1);hoareSort1(a, right + 1, end);return right;
}

⭐int mid = GetMidIndex(a, left, right);
⭐Swap(&a[mid], &a[key]);

• 为什么要Swap？ 如果不Swap↓
  
  因为，最后 a[key] 会和 left 与 right 相遇的数交换，所以 [key] 必须在头部位置。

时间复杂度分析：针对局部有序或有序的情况效率明显提升

时间复杂度为 O(N) = N*logN

<局部优化>

递归到小区间的时候用插入排序

int hoareSort1(int* a, int left, int right)
{assert(a);if (left >= right)return;if ((right - left + 1) < 5){InsertSort(a + left, right - left + 1);}else{int key = left, begin = left, end = right;int mid = GetMidIndex(a, left, right);Swap(&a[mid], &a[key]);while (left < right){while (left < right && a[right] >= a[key]){--right;}while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[key], &a[right]);//left==right//[begin,left-1] [right+1,end]hoareSort1(a, begin, left - 1);hoareSort1(a, right + 1, end);}return right;
}

②挖坑法

思路分析

把选定做 key 的数存储在新变量中。left 和 right 找到 数 填坑里，原位置变新坑。

代码实现

// 快速排序挖坑法
int HoleSort2(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int hole = left, begin = left, end = right;while (left < right){while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[right] = key;//[begin,left-1] [right+1,end]HoleSort2(a, begin, left - 1);HoleSort2(a, right + 1, end);return right;
}

③前后指针法

思路分析

1. cur 找比 key所指向 小的数
2. 找到后，++prev，交换 cur 和 prev 指向的内容
3. cur 走到尽头后，最后交换 key 和 prev

• 小的数往前←，大的数往后→

cur 找到 比 data 小的数时的情况：👇

循环结束的情况：👇

• 示例：
  

代码实现

// 快速排序前后指针法
int PointSort3(int* a, int left, int right)
{assert(a);if (left >= right)return;int keyi = left;int prev = left, cur = left;while (cur <= right){if (a[cur] < a[keyi] && cur != prev)Swap(&a[++prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);//[left,prev-1][prev+1,right]PointSort3(a, left, prev - 1);PointSort3(a, prev + 1, right);return prev;
}

④非递归快排

思路分析

利用数据结构栈 → 广度遍历
递归→ 深度遍历

• 将左右区间[begin,end] 存入栈中
• 循环：
  • 1.取出栈中的左右区间[begin,end]，在这个区间内进行快排
  • 2.一次快排之后，得到两个新的左右区间[begin,end] → [begin,keyi-1] keyi [keyi+1,end]，将其存入栈中（注意顺序）
  • 1.取出栈中的左右区间[keyi+1,end]，在在这个区间内进行快排
  • 2.一次快排之后，得到两个新的左右区间……
  • ……

代码实现

// 快速排序 非递归实现
#include "Stack.h"
void QuickSort(int* a, int left, int right)
{assert(a);Stack st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (!StackEmpty(&st)){int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);int keyi = hoareSort1(a, begin, end);//快排//[begin,keyi-1] keyi [keyi+1,end]if (keyi + 1 < end){StackPush(&st, keyi + 1);StackPush(&st, end);}if (begin < keyi - 1){StackPush(&st, begin);StackPush(&st, keyi - 1);}}StackDestroy(&st);
}

以上代码汇总

// 快速排序递归实现
// 三数取中
int GetMidIndex(int* a, int left, int right)
{int begin = left, end = right;int middle = (left + right) / 2;if (a[begin] < a[end]){if (a[middle] < a[begin])return begin;else if (a[middle] > a[end])return end;elsereturn middle;}else{if (a[middle] < a[end])return end;else if (a[middle] > a[begin])return begin;elsereturn middle;}}
// 快速排序hoare版本
int hoareSort1(int* a, int left, int right)
{assert(a);if (left >= right)return;if ((right - left + 1) < 5){InsertSort(a + left, right - left + 1);}else{int key = left, begin = left, end = right;int mid = GetMidIndex(a, left, right);Swap(&a[mid], &a[key]);while (left < right){while (left < right && a[right] >= a[key]){--right;}while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[key], &a[right]);//left==right//[begin,left-1] [right+1,end]hoareSort1(a, begin, left - 1);hoareSort1(a, right + 1, end);}return right;}// 快速排序挖坑法
int HoleSort2(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int hole = left, begin = left, end = right;while (left < right){while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[right] = key;//[begin,left-1] [right+1,end]HoleSort2(a, begin, left - 1);HoleSort2(a, right + 1, end);return right;
}// 快速排序前后指针法
int PointSort3(int* a, int left, int right)
{assert(a);if (left >= right)return;int keyi = left;int prev = left, cur = left;while (cur <= right){if (a[cur] < a[keyi] && cur != prev)Swap(&a[++prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);//[left,prev-1][prev+1,right]PointSort3(a, left, prev - 1);PointSort3(a, prev + 1, right);return prev;
}// 快速排序 非递归实现
void QuickSort(int* a, int left, int right)
{assert(a);Stack st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (!StackEmpty(&st)){int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);int keyi = hoareSort1(a, begin, end);//[begin,keyi-1] keyi [keyi+1,end]if (keyi + 1 < end){StackPush(&st, keyi + 1);StackPush(&st, end);}if (begin < keyi - 1){StackPush(&st, begin);StackPush(&st, keyi - 1);}}StackDestroy(&st);
}