当前位置：首页 > article >正文

高级排序算法（一）：快速排序详解

article 2025/1/13 3:13:02

引言

当我们处理大规模数据时，像冒泡排序、选择排序这样的基础排序算法就有点力不从心了。这时候，快速排序（Quick Sort）就派上用场了。
作为一种基于分治法的高效排序算法，快速排序在大多数情况下可以在O(n log n)的时间内完成排序。它不仅理论上效率高，而且在实际应用中表现也非常优异，是排序算法中的经典之作。

这篇文章将带你深入理解快速排序的原理、实现细节以及优化策略。

一、快速排序的核心思想

快速排序的核心是分治法（Divide and Conquer），它将问题分为更小的子问题逐一解决。快速排序的主要步骤如下：

选择一个基准值（Pivot）：通常选取数组中的一个元素作为基准。
分区：
- 将小于基准值的元素放到左侧。
- 将大于基准值的元素放到右侧。
递归排序：
- 对左右两个部分分别递归地应用快速排序。

二、快速排序的分区方法

分区是快速排序的核心操作，它直接决定了算法的性能。常见的分区方法有两种：

1. Lomuto分区法

选取数组的最后一个元素作为基准值。
使用一个指针i将数组分为两部分：
- 左侧：小于基准值的元素。
- 右侧：大于基准值的元素。
最后将基准值放到正确的位置。


int lomutoPartition(int arr[], int low, int high) {
    int pivot = arr[high];  // 基准值
    int i = low - 1;        // 指针 i 初始化在 low 的前面

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {  // 如果当前元素小于基准值
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;  // 交换 i 和 j 的元素
        }
    }
    // 将基准值放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;  // 返回基准值的索引
}

2. Hoare分区法

使用两个指针：
- 左指针i从左向右移动，找到第一个大于基准值的元素。
- 右指针j从右向左移动，找到第一个小于基准值的元素。
交换i和j的元素，直到两个指针相遇。
与Lomuto相比，Hoare分区法交换次数更少，适合大规模数据。


int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];  // 基准值
    int i = low - 1;
    int j = high + 1;

    while (1) {
        do {
            i++;
        } while (arr[i] < pivot);  // 从左向右找到大于等于 pivot 的元素

        do {
            j--;
        } while (arr[j] > pivot);  // 从右向左找到小于等于 pivot 的元素

        if (i >= j) return j;  // 指针相遇，返回分区点

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;  // 交换 i 和 j 的元素
    }
}

三、快速排序的完整实现

以下是快速排序的完整实现，使用Lomuto分区法。


#include <stdio.h>

// Lomuto 分区法
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    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);

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

四、快速排序的时间复杂度

快速排序的时间复杂度取决于分区点的选择：

最优情况：每次分区将数组均分为两部分，时间复杂度为 O(n log n)。
最坏情况：每次分区只分出一个元素，时间复杂度为 O(n²)。
平均情况：分区较为均衡，时间复杂度为 O(n log n)。

优化策略：

随机化基准值：随机选择基准值，避免最坏情况。
切换到插入排序：当子数组长度小于一定阈值时，使用插入排序提高效率。

五、快速排序与归并排序的对比

特性	快速排序	归并排序
时间复杂度	平均 O(n log n)，最坏 O(n²)	始终 O(n log n)
空间复杂度	原地排序，O(log n)	O(n)
稳定性	不稳定	稳定
适用场景	数据量大且内存有限	数据量大且对稳定性有要求