快速排序【hoare】--附图示以及代码

霍尔快速排序（Hoare’s Quicksort）详细介绍

一、核心思想

利用分治思想，通过单趟排序，把数组 a 划分成左右两段：

• 左段所有元素 ≤ 枢轴值 a[keyi]
• 右段所有元素 ≥ 枢轴值 a[keyi]

递归地对左右段做同样的处理，最终完成整个数组的排序。

1.1 算法步骤

1.2 霍尔分区的详细步骤

分区准备
当前待分区的区间为 [left, right]。为减少最坏情况出现的概率，代码已使用三数取中法选出中值元素，并将其交换到 a[left] 位置。此后，以 a[keyi] 作为基准值（枢轴），其中 keyi = left。

指针初始化

• 右指针 right 初始指向区间右端点；
• 左指针 left 初始指向区间左端点。

循环扫描与交换
在 left < right 的条件下，反复执行以下流程：

循环不变量
在扫描的全过程中，始终成立：

• 指针 left 左侧（不含 left 本身）的所有元素均 ≤ a[keyi]；
• 指针 right 右侧（不含 right 本身）的所有元素均 ≥ a[keyi]。

分区完成
当左右指针相遇或交错后，记相遇位置为 meeti = left（此时有 left == right）。最后执行一次交换 swap(&a[keyi], &a[meeti])，将基准值放入它在完全排序后的正确位置。函数最终返回 meeti。

此时数组被划分为三个部分：

• a[left_initial … meeti-1]：元素全部 ≤ 基准值；
• a[meeti]：基准值本身，已处于正确排序位置；
• a[meeti+1 … right_initial]：元素全部 ≥ 基准值。

二、动图演示

三、快速排序的复杂度与稳定性分析

时间复杂度

快速排序的时间复杂度取决于每次分区操作的平衡程度，与数据分布密切相关。

• 最好情况：O(n log n)
  当每次选择的基准值（枢轴）都能将数组均匀划分为两个大小相近的子区间时，递归深度为 log n，每层比较次数为 O(n)，总复杂度为 O(n log n)。

• 最坏情况：O(n²)
  当每次选择的基准值都是当前区间的最小值或最大值（例如数组已有序，且未做任何优化）时，每次分区只划分出一个空区间和一个大小为 n-1 的区间，递归深度变为 n，每层比较次数为 O(n)，总复杂度退化为 O(n²)。
  通过 随机选择基准 或 三数取中法 可大幅降低最坏情况出现的概率。

• 平均情况：O(n log n)
  在随机数据下，基准值落在区间中部附近的概率较高，递归树趋于平衡，数学期望为 O(n log n)。快速排序在实际应用中通常表现优异，常数因子较小。

空间复杂度

快速排序的空间消耗主要来自递归调用栈，辅助空间为 O(1)（原地分区）。

• 递归栈深度：
  • 平均情况下，递归深度为 O(log n)，因此空间复杂度为 O(log n)。
  • 最坏情况下（极端不平衡），递归深度为 O(n)，空间复杂度退化为 O(n)。
• 辅助数组：无需额外数组，所有交换在原数组上完成，额外空间仅用于几个临时变量，为 O(1)。

若采用尾递归优化或迭代实现，可将栈空间进一步降低，但最坏情况仍可能达到 O(n)。

稳定性

快速排序是一种 不稳定 的排序算法。

• 原因：在分区过程中，元素通过交换（swap）移动位置，相同的元素可能因为基准值的移动而改变相对顺序。
• 示例：数组 [2a, 1, 2b]（两个相等的 2 分别标记为 a、b），若基准值为 1，则分区后 2b 可能被换到 2a 前面，导致相对顺序变化。

若需保持稳定性，可选择归并排序或插入排序等稳定算法。

四、示例代码

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <assert.h>

//交换
void swap(int* p1, int* p2)
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}

//三数取中
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right–left) / 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// a[left] >= a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
return right;
}
}
//hoare法
int PartSort1(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
swap(&a[left], &a[mid]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right—;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
swap(&a[right], &a[left]);
}
}
int meet = left;
swap(&a[keyi], &a[meet]);
return meet;
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
int n = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = n – 1;

QuickSort(arr, left, right);

for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}

return 0;
}