[!info] related notes 算法面试题型 MOC

快速排序（Quick Sort）

快排的核心是“分区（partition）”：选一个 pivot，把数组分成小于/等于/大于 pivot 的区域，然后递归处理左右。

关键点：pivot 怎么选

• 固定位置选 pivot：最坏情况可能退化到 $O(n^2)$。
• 随机选 pivot：期望时间复杂度 $O(n\log n)$，工程上更稳。

三路划分（荷兰国旗）

当数据里有大量重复值时，三路划分能显著减少递归规模。

维护区间： < pivot | == pivot | > pivot
扫描指针 i 从左到右推进，按 nums[i] 与 pivot 的比较把元素交换到对应区间。

Java Template (Random Pivot + 3-way Partition)

import java.util.*;

public class QuickSort3Way {
    static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr, 0, arr.length - 1);
    }

    static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;
        int pivot = arr[l + (int) (Math.random() * (r - l + 1))];
        int[] range = partition(arr, l, r, pivot);
        quickSort(arr, l, range[0] - 1);
        quickSort(arr, range[1] + 1, r);
    }

    // returns [eqL, eqR] for == pivot range
    static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1;
        int more = r + 1;
        int i = l;
        while (i < more) {
            if (arr[i] < pivot) {
                swap(arr, ++less, i++);
            } else if (arr[i] > pivot) {
                swap(arr, i, --more);
            } else {
                i++;
            }
        }
        return new int[] { less + 1, more - 1 };
    }

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

复杂度

• 平均/期望：$O(n\log n)$
• 最坏：$O(n^2)$（随机化可以极大降低出现概率）
• 额外空间：递归栈平均 $O(\log n)$