快速排序详解

原理

快速排序是一种高效的分治排序算法，其核心思想是选择一个基准元素，将数组划分为两个子数组：小于基准的元素和大于基准的元素，然后递归地对这两个子数组进行排序。

算法步骤：

1. 选择基准：从数组中选择一个元素作为基准（pivot）
2. 分区：重新排列数组，所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面
3. 递归：递归地对基准左右两边的子数组进行快速排序

时间复杂度：

• 平均情况：O(n log n)
• 最坏情况：O(n²) - 当数组已排序且选择最值作为基准时
• 最好情况：O(n log n)

空间复杂度： O(log n) - 递归调用栈
稳定性： 不稳定排序算法

示例

对数组 [38, 27, 43, 3, 9, 82, 10] 进行快速排序：

第一次分区（选择最后一个元素10作为基准）：

原始数组: [38, 27, 43, 3, 9, 82, 10]
基准: 10

分区过程:
i = -1, j从0到5遍历:
j=0: 38>10, i不变 → [38, 27, 43, 3, 9, 82, 10]
j=1: 27>10, i不变 → [38, 27, 43, 3, 9, 82, 10]  
j=2: 43>10, i不变 → [38, 27, 43, 3, 9, 82, 10]
j=3: 3<10, i=0, 交换38和3 → [3, 27, 43, 38, 9, 82, 10]
j=4: 9<10, i=1, 交换27和9 → [3, 9, 43, 38, 27, 82, 10]

最后交换基准: i=2, 交换43和10 → [3, 9, 10, 38, 27, 82, 43]

递归排序左右子数组：

左子数组 [3, 9] 已有序
右子数组 [38, 27, 82, 43] 继续排序:

选择43作为基准:
27<43, 交换38和27 → [27, 38, 82, 43]
82>43, 不交换
交换基准: 交换82和43 → [27, 38, 43, 82]

继续排序 [27, 38] 和 [82]
最终结果: [3, 9, 10, 27, 38, 43, 82]

C语言实现

#include <stdio.h>
#include <stdlib.h>

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数 - Lomuto分区方案
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);      // 较小元素的索引
    
    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);
}

// 分区函数 - Hoare分区方案（更高效）
int partitionHoare(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);
        
        // 从右向左找第一个小于基准的元素
        do {
            j--;
        } while (arr[j] > pivot);
        
        // 如果两个指针相遇
        if (i >= j) {
            return j;
        }
        
        // 交换两个元素
        swap(&arr[i], &arr[j]);
    }
}

// 快速排序主函数
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);
    }
}

// 使用Hoare分区的快速排序
void quickSortHoare(int arr[], int low, int high) {
    if (low < high) {
        int pi = partitionHoare(arr, low, high);
        quickSortHoare(arr, low, pi);
        quickSortHoare(arr, pi + 1, high);
    }
}

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

// 随机选择基准的快速排序（避免最坏情况）
int randomPartition(int arr[], int low, int high) {
    // 在low和high之间随机选择一个索引
    int random = low + rand() % (high - low + 1);
    swap(&arr[random], &arr[high]);  // 将随机元素交换到最后
    return partition(arr, low, high);
}

void quickSortRandom(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        quickSortRandom(arr, low, pi - 1);
        quickSortRandom(arr, pi + 1, high);
    }
}

// 测试代码
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    printArray(arr, arr_size);
    
    quickSort(arr, 0, arr_size - 1);
    
    printf("排序后数组: ");
    printArray(arr, arr_size);
    
    // 测试随机基准版本
    int arr2[] = {38, 27, 43, 3, 9, 82, 10};
    printf("\n随机基准快速排序:");
    printf("\n原始数组: ");
    printArray(arr2, arr_size);
    
    quickSortRandom(arr2, 0, arr_size - 1);
    printf("排序后数组: ");
    printArray(arr2, arr_size);
    
    return 0;
}

快速排序在实际应用中通常比其他O(n log n)算法更快，因为它的内层循环可以在大多数架构上高效实现，且不需要额外的存储空间。