CSP-J 算法基础 快速排序

前言

快速排序（QuickSort）是一种高效的排序算法，由C.A.R. Hoare在1960年提出。它采用分治策略（Divide and Conquer）来将一个大的问题分解为多个更小的问题，从而高效地进行排序。快速排序在最坏情况下的时间复杂度为O(n²)，但在大多数情况下，其时间复杂度为O(n log n)，因此被广泛应用于实际的排序任务中。快速排序的基本思想是通过一个基准元素（pivot）将待排序数组分为两部分，其中一部分的所有元素都小于基准元素，另一部分的所有元素都大于基准元素，然后递归地对这两部分进行排序。

分治思想

分治思想是一种解决复杂问题的方法，它的核心思路就是把一个大问题分成若干个较小的、相对独立的子问题，分别解决这些小问题，再将它们的结果合并，得到整个问题的解。

什么时候使用分治法？

• 问题可以被分解成相似的小问题：如果问题能够拆分成规模较小的同类问题，这就适合用分治法。比如归并排序，排序一个大数组可以拆分成两个小数组排序。
• 子问题独立解决：这些小问题之间没有太多依赖，可以单独处理。比如在二分查找中，判断出目标值在哪一半后，可以忽略另一半。
• 可以通过合并子问题的结果解决原问题：各个子问题的解可以组合起来得到整个问题的解。比如在求最大子数组和时，可以通过左半部分、右半部分和中间部分的最大值得出整体的最大值。

举几个例子：

1. 归并排序
   归并排序就是一个典型的分治算法。它先把数组分成两半，分别对两部分排序，然后把它们合并在一起。每次的合并操作都是将两个已经排好序的子数组组合成一个有序的数组，最终得到完整的有序数组。

2. 二分查找
   当你在一个排好序的数组中查找一个目标数时，可以通过将数组一分为二，检查中间的值。如果中间的值比目标值大，就在左半部分继续查找；如果比目标值小，就在右半部分查找。这个过程不断地将问题规模缩小，直到找到目标数。

3. 快速排序
   快速排序也是一种分治算法。它首先选择一个基准数（通常是数组中的一个值），然后将数组划分为两部分：比基准数小的放一边，比基准数大的放另一边。接着，对左右两部分分别进行递归排序，最终合并成一个有序数组。

4. 最大子数组问题
   这个问题是找出数组中具有最大和的连续子数组。可以将数组分成两半，分别求解左半部分、右半部分和跨越中间部分的最大子数组，然后取三者中的最大值。

分治法的核心就是将大问题“拆分”成可以“独立”解决的“小问题”，然后把各个小问题的解“合并”成最终结果。这种方法特别适合处理递归问题，或是那些在分解后可以并行处理的情况。

快速排序

快速排序（Quicksort）是一种高效的排序算法，它通过递归地分解问题来排序。其基本原理是分治思想，具体过程如下：

1. 选择基准值（Pivot）：从数组中选取一个元素作为基准值（通常可以选择第一个、最后一个、中间的元素，或者随机选择）。
2. 分区（Partition）：将数组中的其他元素与基准值进行比较，比基准值小的放到它的左边，比基准值大的放到它的右边。此时，基准值的位置就固定了。
3. 递归排序：对基准值左右的两个子数组，分别递归执行上述步骤，直到子数组的长度为1或0，表示无需继续排序。

具体例子

我们用数组 [8, 3, 1, 7, 0, 10, 2] 来演示快速排序的过程。

步骤 1：选择基准值

假设选择数组的第一个元素 8 作为基准值。

步骤 2：分区

把剩下的元素与基准值 8 比较：

• 小于 8 的放在左边：[3, 1, 7, 0, 2]
• 大于 8 的放在右边：[10]

分区后，数组变为：[3, 1, 7, 0, 2] [8] [10]

步骤 3：递归排序左边部分 [3, 1, 7, 0, 2]

选取左边数组的第一个元素 3 作为基准值，进行分区：

• 小于 3 的放左边：[1, 0, 2]
• 大于 3 的放右边：[7]

分区后，左边数组变为：[1, 0, 2] [3] [7]

步骤 4：递归排序 [1, 0, 2]

选取 1 作为基准值，进行分区：

• 小于 1 的放左边：[0]
• 大于 1 的放右边：[2]

分区后：[0] [1] [2]

至此，左边部分已经排好序：[0, 1, 2]

步骤 5：合并左边部分

将排好序的左边部分与之前的基准值 3 和右边部分 [7] 合并：
[0, 1, 2, 3, 7]

步骤 6：合并整个数组

最后，将左边排序好的部分 [0, 1, 2, 3, 7] 与基准值 8 和右边部分 [10] 合并，得到最终结果：
[0, 1, 2, 3, 7, 8, 10]

快速排序的步骤总结：

1. 选定基准值；
2. 分区为两个子数组；
3. 递归排序子数组；
4. 合并排序结果。

这个过程展示了如何通过反复分解和排序来将数组有序化。

当右边部分有两个及以上的元素时，分区过程和排序步骤类似，只不过要处理更多的元素。让我们用一个例子详细解释一下：

假设我们有数组 [8, 3, 1, 7, 0, 10, 2, 12, 9]，选择 8 作为基准值，进行分区和排序：

快速排序的第二个例子

初始状态

原始数组：[8, 3, 1, 7, 0, 10, 2, 12, 9]

第一步：分区

选择 8 作为基准值，将数组分为两部分：

• 小于 8 的元素：[3, 1, 7, 0, 2]
• 大于 8 的元素：[10, 12, 9]

分区后数组变为：[3, 1, 7, 0, 2] [8] [10, 12, 9]

第二步：递归排序右边部分 [10, 12, 9]

选择基准值

选择右边部分的第一个元素 10 作为基准值。

分区

将右边部分 [10, 12, 9] 与基准值 10 比较：

• 小于 10 的放左边：[9]
• 大于 10 的放右边：[12]

分区后数组变为：[9] [10] [12]

至此，右边部分已经排好序。

第三步：递归排序左边部分 [3, 1, 7, 0, 2]

选择基准值

选择左边部分的第一个元素 3 作为基准值。

分区

将左边部分 [3, 1, 7, 0, 2] 与基准值 3 比较：

• 小于 3 的放左边：[1, 0, 2]
• 大于 3 的放右边：[7]

分区后左边部分变为：[1, 0, 2] [3] [7]

递归排序 [1, 0, 2]

选择基准值

选择 1 作为基准值。

分区

将 [1, 0, 2] 与基准值 1 比较：

• 小于 1 的放左边：[0]
• 大于 1 的放右边：[2]

分区后：[0] [1] [2]

最终合并

将排好序的部分合并：

• 左边部分：[0, 1, 2, 3, 7]
• 中间部分：[8]
• 右边部分：[9, 10, 12]

最终得到排序后的数组：[0, 1, 2, 3, 7, 8, 9, 10, 12]

总结

1. 选择基准值：从数组中选择一个元素作为基准值。
2. 分区：将数组分成两部分，一部分小于基准值，另一部分大于基准值。
3. 递归排序：对分区后的每个子数组递归执行相同的步骤。
4. 合并：将排序好的子数组合并成最终结果。

这种方法利用递归将问题分解成小问题，逐步解决，每次处理的子数组规模逐渐减小，直到每个子数组都只包含一个元素或为空，最终得到有序的数组。

时间与空间复杂度

快速排序（Quicksort）是一种高效的排序算法，其时间和空间复杂度如下：

时间复杂度

1. 平均时间复杂度：

   • O(n log n)：这是快速排序在大多数情况下的时间复杂度。其原因是每次分区操作将问题规模减少一半，而分区操作需要遍历数组，因此在大多数情况下，快速排序的时间复杂度是 O(n log n)。

2. 最坏时间复杂度：

   • O(n^2)：最坏情况下，快速排序的时间复杂度为 O(n^2)。最坏情况发生在每次选择的基准值都是当前数组的最小值或最大值，导致每次只能将一个元素固定到正确位置，这样分区操作不均匀，最终导致时间复杂度为平方级别。例如，当数组已经是排序好的或完全逆序时，选择的基准值可能会导致最坏情况。

3. 最好时间复杂度：

   • O(n log n)：在最佳情况下，基准值总能将数组分成接近均等的两个部分，每次分区都能将问题规模减半，从而使时间复杂度达到 O(n log n)。

空间复杂度

1. 空间复杂度：
   • O(log n)：快速排序的空间复杂度主要取决于递归调用的深度。在平均情况下，递归调用的深度是 O(log n)，因为每次分区将问题规模减少一半。然而，由于递归的调用栈的深度可以达到 n（在最坏情况下），空间复杂度可能达到 O(n)，但通常情况下是 O(log n)。

总结：

• 时间复杂度：

  • 最好情况：O(n log n)
  • 平均情况：O(n log n)
  • 最坏情况：O(n^2)

• 空间复杂度：

  • 平均情况：O(log n)
  • 最坏情况：O(n) (主要是递归调用栈的深度)

快速排序在实际应用中通常表现得非常高效，特别是在平均情况下，因为它能快速地将大部分元素定位到正确的位置。然而，选择适当的基准值（例如使用随机选择或“三数取中法”）可以有效减少最坏情况发生的可能性，提高算法的实际性能。

编程实现快速排序

#include <stdio.h>

// 函数声明
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void printArray(int arr[], int size);

int main() {
    int arr[] = { 8, 3, 1, 7, 0, 10, 2, 12, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：");
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    printf("排序后的数组：");
    printArray(arr, size);

    return 0;
}

/*
low：表示待排序子数组的起始索引。
high：表示待排序子数组的结束索引（包括该索引）。
*/
// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        //pi就是i+1:第一次分组的分界线
        int pi = partition(arr, low, high);

        printf("基准值的索引位置：%d\n", pi);
        printf("排序后数组的状态：");
        printArray(arr, high + 1);

        quickSort(arr, low, pi - 1);  // 对基准值左侧的子数组进行排序
        quickSort(arr, pi + 1, high); // 对基准值右侧的子数组进行排序
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准值
    int i = (low - 1);     // 小于基准值的元素的索引

    printf("基准值：%d\n", pivot);

    //与基准值比较并互换位置
    for (int j = low; j <= high - 1; j++) {
        printf("i:%d pivot:%d arr[j]:%d j:%d\n", i, pivot, arr[j],j);
        if (arr[j] < pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;

            printf("交换元素：%d 和 %d\n", arr[i], arr[j]);
            printf("数组状态：");
            printArray(arr, high + 1);
        }
    }
    // 交换基准值与 arr[i + 1]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    printf("将基准值 %d 移到索引 %d\n", arr[i + 1], i + 1);
    printf("数组状态：");
    printArray(arr, high + 1);

    return (i + 1);
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

总结

在实现快速排序时，关键步骤包括选择基准元素、分区操作和递归排序。通过不断选择基准元素并将数组分区，快速排序将问题规模逐步减小，最终实现排序。快速排序的效率受基准选择的影响较大，选择好的基准元素可以显著提高排序性能。尽管最坏情况下的时间复杂度为O(n²)，适当的优化（如随机选择基准元素或使用“三数取中法”）可以有效避免这种情况，使其在实际应用中表现出色。通过这些优化，快速排序成为一种高效、实用的排序算法，广泛应用于各种计算机科学和工程领域。