《快速排序》

快速排序（Quick Sort）是一种基于分治思想的排序算法。通过一趟排序把数据分割成独立的两部分，其中一部分的所有数据都比另一部分小，再递归地对这两部分继续排序，最终使整个序列有序。

1 算法思想

快速排序的核心是 partition（划分） 操作：

在待排序数列中选择一个基准数（pivot）（通常取第一个或最后一个元素）；
把小于等于基准的数移动到左边，把大于等于基准的数移动到右边（两种分区方式略有差异）；
基准数最终落在「正确」的位置；
递归地对左右两个分区重复上述过程，直到每个分区只剩一个数。

2 复杂度分析

平均/最好时间复杂度：O(n log n)（每次划分大致将数列分成两半）；
最坏时间复杂度：O(n^2)（每次划分都极不平衡，例如对有序数组且固定取首/尾元素为基准）；
空间复杂度：O(log n)（递归调用栈深度）；
稳定性：不稳定，partition 过程中相同元素的相对顺序可能被改变。

优化手段：随机选择基准、三数取中、小数组改用插入排序、三路快排（处理大量重复元素）。

3 实现（C++）

下面的例子取数组最右边的元素作为基准，pivot_index 指向分区边界：

        
      
#include <stdio.h>

void swap(int arr[], int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 以 arr[high] 为基准，把小于基准的元素放到左边并返回基准的最终位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int pivot_index = low;
    for (int j = low; j < high; j++) {
        // 升序
        if (arr[j] < pivot) {
            swap(arr, pivot_index, j);
            pivot_index++;
        }
        // 降序：if (arr[j] > pivot) { ... }
    }
    swap(arr, pivot_index, high);
    return pivot_index;
}

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);
    }
}

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

int main() {
    int arr[] = {1, 3, 2, 4, 5, 6, 7};
    int n = 7;
    quickSort(arr, 0, n - 1);
    printArray(arr, n);
    return 0;
}

4 实现（Python）

        
      
def partition(arr, low, high):
    """以 arr[high] 为基准，返回基准最终所在位置"""
    pivot = arr[high]
    pivot_index = low
    for i in range(low, high):
        if arr[i] < pivot:
            arr[i], arr[pivot_index] = arr[pivot_index], arr[i]
            pivot_index += 1
    arr[high], arr[pivot_index] = arr[pivot_index], arr[high]
    return pivot_index


def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        quick_sort(arr, 0, n - 1)
        print(' '.join(map(str, arr)))

5 与「最小的 k 个数」的关系

快速排序的 partition 思想常被用于 Top-K 问题：在 partition 返回基准位置 pi 后，如果 pi 恰好等于 k，则 arr[0:k] 就是最小的 k 个数（无序），无需对两侧完全排序。

        
      
def smallest_k(arr, k):
    if not arr or k <= 0:
        return []
    low, high = 0, len(arr) - 1
    while low <= high:
        pi = partition(arr, low, high)
        if pi == k - 1:
            return arr[:k]
        elif pi < k - 1:
            low = pi + 1
        else:
            high = pi - 1
    return arr[:k]

这样得到的复杂度为平均 O(n)（即快速选择 quick select），常作为「最小的 k 个数」这类面试题的解法。

6 参考文档

阅读 — · 全站 —