排序练习：快速排序

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

// 交换两个整型变量
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}

// 快速排序 Hoare 分区版本
int PartSort1(int* a, int left, int right)
{
// 选定最右侧元素作为基准值下标
int key = right;

while (left < right)
{
// 基准在右侧，左指针先走：找大于基准的数
while (left < right && a[left] <= a[key])
{
left++;
}

// 右指针后走：找小于基准的数
while (left < right && a[right] >= a[key])
{
right–;
}

// 交换左右指针指向元素
Swap(&a[left], &a[right]);
}

// 基准归位，返回基准下标
Swap(&a[left], &a[key]);
return left;
}

// 快速排序递归函数
void QuickSort(int* a, int left, int right)
{
assert(a); // 数组判空断言

// 区间只剩一个/无元素，直接返回
if (left >= right)
{
return;
}

// 获取基准元素下标
int keyi = PartSort1(a, left, right);
// 递归处理左区间
QuickSort(a, left, keyi – 1);
// 递归处理右区间
QuickSort(a, keyi + 1, right);
}

int main()
{
int arr[] = {1, 16, 13, 66, 54, 52};
int len = sizeof(arr) / sizeof(arr[0]);

// 原代码错误：len-2 会漏掉最后一个元素，修正为 len – 1
QuickSort(arr, 0, len – 1);

// 遍历打印排序后数组
for (int i = 0; i < len; i++)
{
printf("%d\\t", arr[i]);
}
printf("\\n");

return 0;
}