快速排序（Quick Sort）是一种高效的排序算法，由东尼·霍尔于1960年提出。它是一种基于分治法的比较排序算法，通常会比其他O(n²)的算法（如冒泡排序、选择排序）要快。本文将详细介绍快速排序的工作原理，并提供如何在C语言中实现快速排序的示例。

快速排序的基本思想

快速排序的核心思想是：通过选择一个“基准值”（pivot），将待排序数组划分成两部分，左边的元素都比基准值小，右边的元素都比基准值大；然后递归地对这两部分继续进行排序。最终，整个数组便是有序的。

具体步骤

  1. 选择基准值（Pivot）：从数组中选择一个元素作为基准值，可以是第一个元素、最后一个元素、随机元素，或更复杂的“三数取中法”选择的元素。

  2. 分区操作：重排数组，使得基准值左边的元素均小于它，右边的元素均大于它。此过程称为“分区”（Partitioning），完成后基准值会处于其正确的排序位置。

  3. 递归排序：对基准值左边和右边的子数组递归地进行快速排序。

C语言实现快速排序

下面是快速排序在C语言中的一个简单实现：

#include <stdio.h>

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

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (array[j] <= pivot) {
            i++;    // 增加较小元素的索引
            // 交换array[i]和array[j]
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    // 交换array[i + 1]和array[high] (或 pivot)
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return (i + 1);
}

// 快速排序函数
void quickSort(int array[], int low, int high) {
    if (low < high) {
        // pi是分区索引，array[pi]已经排好序
        int pi = partition(array, low, high);

        // 分别排序两个子数组
        quickSort(array, low, pi - 1);
        quickSort(array, pi + 1, high);
    }
}

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

// 主函数
int main() {
    int data[] = {8, 7, 2, 1, 0, 9, 6};
    int n = sizeof(data) / sizeof(data[0]);
    printf("Unsorted Array:\n");
    printArray(data, n);
    quickSort(data, 0, n - 1);
    printf("Sorted array in ascending order:\n");
    printArray(data, n);
    return 0;
}

分析与优化

时间复杂度

快速排序的平均时间复杂度为O(n log n)，这是因为每次划分的过程需要O(n)时间，总共需要进行O(log n)次划分。然而，在最坏的情况下（每次选择的基准都是数组的最大或最小值，此时递归的调用深度为O(n)），快速排序的时间复杂度退化为O(n²)。

空间复杂度

快速排序的空间复杂度为O(log n)，主要是递归调用时需要的栈空间。不过，在没有实现尾递归优化的情况下，最坏情况下空间复杂度也会退化为O(n)。

优化策略

  1. 选取合适的基准：使用“三数取中法”或随机选择基准值，能有效避免最坏情况的发生。

  2. 小数组优化：对于小规模的数组（如少于10个元素），可以用插入排序来替代快速排序，以提高性能。

  3. 尾递归优化：在一些编译器中，可通过改写递归为迭代形式来优化对栈空间的使用。

总结

快速排序是一种高效的排序算法，尤其在处理大规模数据时表现突出。本文介绍了其基本思想、工作原理以及在C语言中的实现方式。通过主要关注基准选择和分区操作的优化，可以进一步提升其性能。快速排序不仅是面试中的高频考点，也是开发中常用的算法之一，精通它会大大提高我们处理相关问题的能力。