【数据结构】快速排序算法精髓解析

1.快速排序

1.1Hoare 版本

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中

的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

下面我们先理解快速排序排一趟的过程：

如果选择最右边的值让右边的 end 先走

选择最右边的值作为 key 需要 begin 先走，不然排序会出问题

找大是找一个比基准值 key 大的数，第一个数是 6 比 5 大，end 找到比基准值小的数 4 时，将 4 和 6 交换

到达中间位置时将中间数据和 key 交换

一趟我们就可以把一个数组分成三个部分比 key 小的子数组，key，比 key 大的子数组

如果要将一个数组排成升序，我们可以利用递归的思想，不断进行单趟，直到 key 的左右只有一个数据的时候，整个数组就都有序了；（下图是理想的划分情况，key 处于正中间的位置，实际情况 key 可能不在正中间位置，但是不影响我们递归实现，只要 key 左边的数都比 key 小，右边的都比 key 大就行）

加上三数取中后可以避免快速排序的缺陷（即 key 取到最大或最小）

// 快速排序递归实现 
// 快速排序hoare版本 
//时间复杂度：O(N*logN-N^2)// 三数取中：确定中间值索引后只做一次交换
void GetMid(int* a, int begin, int end)
{int mid = begin + (end - begin) / 2; // 计算中间索引// 比较三个值，确定中间值的索引，无需实际排序if ((a[begin] <= a[mid] && a[mid] <= a[end]) ||(a[end] <= a[mid] && a[mid] <= a[begin])){// mid是中间值，交换mid和endswap(&a[mid], &a[end]);}else if ((a[mid] <= a[begin] && a[begin] <= a[end]) ||(a[end] <= a[begin] && a[begin] <= a[mid])){// begin是中间值，交换begin和endswap(&a[begin], &a[end]);}// 若end是中间值，则无需交换（本身就在end位置）
}//最坏的情况是key每次都取到最大或最小的数,可以加入三数取中避免
int PartSort1(int* a, int begin, int end)
{GetMid(a, begin, end);int keystatue = end;while (begin < end){//当begin和end相遇就停下while (begin < end && a[keystatue] >= a[begin]){begin++;}while (begin < end && a[keystatue] <= a[end]){end--;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[keystatue]);return begin;
}void QuickSort1(int* a, int left, int right)
{assert(a);if (left >= right)return;int div = PartSort1(a, left, right);QuickSort1(a, left, div - 1);QuickSort1(a, div + 1, right);
}

1.2快速排序（挖坑法）

性能上和 Hoare 版本的快速排序没什么区别，只是实现方法有所差异

实现的步骤

Step 1：选基准值，挖第一个坑

  用三数取中法（GetMid）从 a[begin]、a[mid]、a[end] 中选中间值，交换到 end 位置（作为基准值）。

  记录基准值 key = a[end]，此时 end 位置成为第一个 “坑”（需要被填充）。

Step 2：左指针找大值，填右坑

  左指针 begin 从左向右遍历，找到第一个 大于 key 的元素（a[begin] > key）。

  将该元素填入当前的 “坑”（初始是 end 位置），即 a[end] = a[begin]。

  此时 begin 位置变成新的 “坑”（因为元素被移走了）。

Step 3：右指针找小值，填左坑

  右指针 end 从右向左遍历，找到第一个 小于 key 的元素（a[end] < key）。

  将该元素填入当前的 “坑”（上一步的 begin 位置），即 a[begin] = a[end]。

  此时 end 位置变成新的 “坑”。

Step 4：重复填坑，直到指针相遇

  循环执行 Step 2 和 Step 3，不断移动 begin 和 end，直到 begin == end（两指针相遇）。

  此时相遇的位置就是基准值 key 的最终位置，将 key 填入该位置（a[begin] = key）。

//挖坑法
int PartSort2(int* a, int begin, int end)
{GetMid(a, begin, end);int key = a[end];while (begin < end){while (begin < end && a[begin] <= key){begin++;}a[end] = a[begin];while (begin < end && a[end] >= key){end--;}a[begin] = a[end];}a[begin] = key;return begin;
}

1.3快速排序（前后指针法）

这里我key选end下标的数据，cur指针开始指向待排序列的头，prev指向cur的前一个位置

当cur遇到比key小的数，prev++，交换cur和prev的数据

当cur遇到比key大的数时cur++，prev++和prev进行交换

cur遇到比key小的数，prev++，交换cur和prev的数据

最后prev指针的数据左边比它小，右边比它大

1.初始化指针：

          prev = begin - 1：初始时 “小于基准值区域” 为空，指向区域外。

          cur = begin：从数组起始位置开始遍历。

          keyindex = end：选最右元素作为基准值（建议先用三数取中优化）。

2.遍历与分区：

      当cur < end（未遍历到基准值）：

            若a[cur] < 基准值：prev++（扩大 “小于区域”），交换a[prev]和a[cur]（将当前元素              加入小于区域）。    无论是否交换，cur++（继续遍历下一个元素）。

3.放置基准值：

        遍历结束后，prev指向 “小于区域” 的最后一个元素，prev + 1是基准值的正确位置。

         交换prev + 1与keyindex（基准值位置），此时基准值左边全小于它，右边全大于等于               它。

4.返回基准值位置：prev + 1（即prev自增后的值）。

// 前后指针法分区函数
int PartSort3(int* a, int begin, int end)
{// 三数取中优化（可选，建议加上）GetMid(a, begin, end);int keyindex = end;  // 基准值索引（选end位置元素）int prev = begin - 1;  // 前指针：指向小于基准值区域的最后一个元素int cur = begin;      // 后指针：遍历数组找小于基准值的元素// 遍历到基准值前一个位置即可while (cur < end){// 若当前元素小于基准值，扩展小于区域if (a[cur] < a[keyindex]){prev++;  // 前指针右移（扩大小于区域）swap(&a[prev], &a[cur]);  // 交换到小于区域}// 无论是否交换，后指针都要右移（继续遍历）cur++;}// 最后将基准值放到小于区域的后面（prev+1）prev++;swap(&a[prev], &a[keyindex]);return prev;  // 返回基准值最终位置
}

2.快速排序非递归实现

递归最大的缺陷是如果栈帧的深度太深，可能会导致栈溢出

创建栈并初始化（StackInit）。

将整个数组的左右边界[left, right]入栈（注意栈是 “后进先出”，先推右边界，再推左边界）。

循环处理：栈非空时持续分割区间

关键：每次从栈中取出一个区间，用PartSort3（前后指针法）分区，确定基准值的最终位置div，将区间一分为二。

子区间入栈：处理未排序的部分

分区后，需判断左右子区间是否需要继续排序（长度 > 1 时才需要），并将有效子区间入栈

逻辑：子区间长度≤1 时（div+1 >= end 或 begin >= div-1），已天然有序，无需入栈。

当栈为空时，所有区间均已处理（均为有序的小区间），排序完成。

最后销毁栈（StackDestroy），释放资源。

“栈存区间→出栈分区→有效子区间入栈→循环至栈空”，通过栈模拟递归的 “先分右、再分左” 的处理顺序，最终实现整个数组有序。

// 快速排序非递归实现 
void QuickSortNonR(int* a, int left,int right)
{ST st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)) {// 出栈获取当前待处理区间[begin, end]int begin = StackTop(&st); StackPop(&st);  // 先出左边界int end = StackTop(&st); StackPop(&st);    // 再出右边界// 核心：分区操作（前后指针法）int div = PartSort3(a, begin, end);  // 得到基准值位置div// 此时数组分为：[begin, div-1]（≤基准值） 和 [div+1, end]（≥基准值）// 右子区间[div+1, end]入栈（若长度>1）if (div + 1 < end) {StackPush(&st, end);       // 先推右边界StackPush(&st, div + 1);   // 再推左边界}// 左子区间[begin, div-1]入栈（若长度>1）if (begin < div - 1) {StackPush(&st, div - 1);   // 先推右边界StackPush(&st, begin);     // 再推左边界}StackDestroy(&st);}

快速排序的特性总结：

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

时间复杂度：O(N*logN)