快 速 排 序

标签： int 元素 low 数组 枢纽 排序

快速排序（Quick Sort）是一种高效的基于分治法的排序算法。它通过递归地将数组分成更小的子数组进行排序，最终使整个数组有序。

快速排序的基本思想

1. 选择枢纽元（Pivot）： 从数组中选择一个元素作为枢纽元。
2. 分区（Partition）： 将数组分成两部分，一部分元素都小于枢纽元，另一部分元素都大于枢纽元。
3. 递归排序（Recursion）： 递归地对两个子数组进行快速排序，直到子数组的大小为1或0。

快速排序的步骤

1. 选择枢纽元

选择枢纽元的方法有多种，常见的包括：

• 固定选择法： 选择第一个元素、最后一个元素或中间元素。
• 随机选择法： 随机选择一个元素作为枢纽元。
• 三数取中法： 选择第一个、最后一个和中间位置的元素，取这三个数的中值作为枢纽元。

2. 分区过程

分区过程的目标是重新排列数组，使得枢纽元左边的所有元素小于枢纽元，右边的所有元素大于枢纽元。以下是一个典型的分区算法：

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为枢纽元
    int i = low - 1;  // i是较小元素的索引

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;  // 增加较小元素的索引
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

3. 递归排序

通过递归调用快速排序函数，对分区后的子数组进行排序。

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // 递归地对分区后的子数组进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

4. 完整代码示例

以下是一个完整的快速排序的C++实现：

#include <iostream>
using namespace std;

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

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;  // 增加较小元素的索引
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // 递归地对分区后的子数组进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

快速排序的时间复杂度

快速排序的时间复杂度分析如下：

• 最优情况： O(n log n) 最优情况发生在每次分区时，枢纽元正好将数组分成大小接近相等的两部分。
• 最坏情况： O(n^2) 最坏情况发生在每次分区时，枢纽元总是数组中最大或最小的元素，这会导致每次只分割出一个元素的情况，如对已经有序的数组进行排序。
• 平均情况： O(n log n) 在大多数情况下，快速排序的时间复杂度接近于O(n log n)，这也是其相比其他排序算法的优势所在。

快速排序的优化

1. 随机化枢纽元选择： 通过随机选择枢纽元，可以有效避免最坏情况。
2. 三数取中法： 通过选择三个数的中值作为枢纽元，可以更好地分割数组。
3. 尾递归优化： 在递归调用时，先对较小的子数组进行排序，可以减少递归深度，从而优化性能。

总结

快速排序是一种高效的排序算法，具有平均O(n log n)的时间复杂度。其核心思想是分治法，通过选择枢纽元将数组分成两部分，然后递归地对每部分进行排序。虽然在最坏情况下时间复杂度为O(n^2)，但通过随机化枢纽元选择和其他优化方法，可以在实际应用中有效避免最坏情况。快速排序由于其简单、高效的特点，广泛应用于各种计算机系统中。

标签：,int,元素,low,数组,枢纽,排序
From： https://blog.csdn.net/m0_74091159/article/details/139378015