[排序算法]快速排序

1.基本思想

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

        下面是快速排序算法的核心实现部分，采用了分治的思想。先通过 _QuickSort 函数对当前区间进行划分，确定基准值的最终位置，然后递归地对基准值左右两侧的子区间进行排序，直到整个数组有序。

// 快速排序函数，用于对数组指定区间内的元素进行排序
// 参数 a 是待排序数组的指针
// 参数 left 是当前待排序区间的左边界索引
// 参数 right 是当前待排序区间的右边界索引
void QuickSort(int* a, int left, int right)
{
    // 如果左边界大于等于右边界，说明当前区间为空或者只有一个元素
    // 此时不需要再进行排序，直接返回
    if (left >= right) {
        return;
    }
    // 调用 _QuickSort 函数，该函数用于按照基准值将区间 [left, right) 中的元素进行划分
    // 划分后，基准值会被放置到其最终的正确位置，该位置的索引由 meet 接收
    int meet = _QuickSort(a, left, right);
    // 对基准值左边的子区间 [left, meet - 1] 递归调用 QuickSort 函数进行排序
    QuickSort(a, left, meet - 1);
    // 对基准值右边的子区间 [meet + 1, right] 递归调用 QuickSort 函数进行排序
    QuickSort(a, meet + 1, right);
}

2.hoare版本

算法思路：

1.创建左右指针，确定基准值

2.从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环

代码实现：

#include <stdio.h>

// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数，用于将数组 a 中从 left 到 right 区间的元素按照基准值进行划分
// 返回值为基准值最终所在的位置
int _QuickSort(int* a, int left, int right) {

    // 选择最左边的元素作为基准值的索引
    int keyi = left;
    // 左指针从基准值的下一个位置开始
    ++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[left++], &a[right--]);
        }
    }

    // 当左右指针相遇后，将基准值与右指针所指向的元素交换位置
    // 此时右指针所在的位置就是基准值最终应该所在的位置
    swap(&a[keyi], &a[right]);

    // 返回基准值最终所在的位置，用于后续递归排序
    return right;
}

// 封装的快速排序函数，递归调用 _QuickSort 函数
void QuickSort(int* a, int left, int right) {
    if (left < right) {
        // 调用 _QuickSort 函数进行分区，得到基准值的最终位置
        int key = _QuickSort(a, left, right);
        // 递归对基准值左边的子数组进行排序
        QuickSort(a, left, key - 1);
        // 递归对基准值右边的子数组进行排序
        QuickSort(a, key + 1, right);
    }
}

// 测试代码
int main() {
    int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 调用封装的快速排序函数
    QuickSort(arr, 0, n - 1);

    // 输出排序后的数组
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

3.小试牛刀

         题目链接：P1223 排队接水 - 洛谷

    3.1解题思路

        这道题的核心思路是让接水时间短的人先接水，从而使总的等待时间最短，平均等待时间也最小。

    3.2代码

        本题可使用多种排序方法，这里我使用的是快速排序：

#include <stdio.h>

// 定义 Person 结构体
typedef struct {
    int number;  // 编号
    int time;    // 接水时间
} Person;

// 交换两个 Person 结构体的值
void swap(Person *a, Person *b) {
    Person temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数，用于对 Person 结构体数组进行分区
int _QuickSort(Person *a, int left, int right) {
    int keyi = left;
    int leftPtr = left + 1;
    int rightPtr = right;

    while (leftPtr <= rightPtr) {
        // 从右向左找小于基准值（基准 Person 的接水时间）的元素
        while (leftPtr <= rightPtr && a[rightPtr].time > a[keyi].time) {
            rightPtr--;
        }
        // 从左向右找大于基准值（基准 Person 的接水时间）的元素
        while (leftPtr <= rightPtr && a[leftPtr].time < a[keyi].time) {
            leftPtr++;
        }

        if (leftPtr <= rightPtr) {
            // 交换满足条件的元素
            swap(&a[leftPtr++], &a[rightPtr--]);
        }
    }
    // 将基准元素放到正确位置
    swap(&a[rightPtr], &a[keyi]);
    return rightPtr;
}

// 快速排序函数，递归调用 _QuickSort 函数对 Person 结构体数组排序
void QuickSort(Person *a, int left, int right) {
    if (left < right) {
        int key = _QuickSort(a, left, right);
        // 递归排序基准元素左边的部分
        QuickSort(a, left, key - 1);
        // 递归排序基准元素右边的部分
        QuickSort(a, key + 1, right);
    }
}

int main() {
    int n;  // 排队人数
    Person people[1001] = {0};
    double total = 0;

    // 读取排队人数
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        // 读取每个人的接水时间
        scanf("%d", &people[i].time);
        // 实际编号为数组编号加 1
        people[i].number = i + 1;
    }

    // 调用快速排序函数对 people 数组按接水时间排序
    QuickSort(people, 0, n - 1);

    // 输出队列序号
    for (int i = 0; i < n; i++) {
        printf("%d ", people[i].number);
    }

    // 计算排队时间并输出
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            total += people[j].time;
        }
    }
    printf("\n%.2lf", total / n);

    return 0;
}

4.疑难解答

   4.1 为什么跳出循环后right位置的值一定不大于key？

      原理分析

        在分区函数里，left 从左往右找大于等于基准值 key 的数，right 从右往左找小于等于 key 的数，二者不断交换元素。当 left > right 跳出循环时，意味着 right 到了 left 左侧。而 left 扫描过的数都不大于 key，所以 right 指向的数也必然不大于 key。

---

     举例说明

 假设有数组 [3, 1, 4, 2]，选 3 作基准值 key。

• 初始：left 指向 1，right 指向 2。
• 移动：right 停在 2（小于等于 3），left 停在 4（大于等于 3），交换得 [3, 1, 2, 4]。
• 再移动：right 左移一位，left 右移一位，此时 left > right，right 指向 2（不大于 3）。 综上，跳出循环后 right 位置的值一定不大于 key。

   4.2 为什么left 和 right指定的数据和key值相等时也要交换？

原理分析

        在 Hoare 版本的快速排序分区算法中，left 指针从左向右寻找大于等于基准值 key 的元素，right 指针从右向左寻找小于等于基准值 key 的元素，当两指针都找到符合条件的元素时就进行交换。若遇到和 key 相等的元素不交换，会破坏分区的逻辑，导致基准值无法正确归位，最终影响整个排序的正确性。

---

反例说明

        假设有数组 [3, 3, 1, 2, 3]，选择第一个元素 3 作为基准值 key。

若相等元素不交换

• 初始状态：left 指向第二个 3，right 指向最后一个 3。
• 第一次指针移动：
  • right 指针向左移动，由于不交换相等元素，它会跳过等于 3 的元素，直到找到 2 才停止。
  • left 指针向右移动，同样跳过等于 3 的元素，停在 1 处。此时两指针位置符合交换条件，交换 1 和 2，数组变为 [3, 3, 2, 1, 3]。
• 后续指针移动与分区结果：继续移动指针，最终基准值 3 归位时，无法将数组正确地分为小于等于 3 和大于等于 3 的两部分。例如，可能会出现基准值位置错误，使得后续递归排序时左右子数组划分混乱，导致整个排序结果错误。

-------有问题欢迎私信和评论------