← 返回首页 📖 📖 Wiki知识库
📐 学习维度 本篇是 📖 📖 Wiki知识库 🏠 首页 🛤️ 学习路径 📚 全部文章

Java排序算法面试手写精讲 - 二、快速排序(面试必手写)

本文是 Java排序算法面试手写精讲 的分章阅读版。

二、快速排序(面试必手写)

核心思想

分治:选一个基准值(pivot),将数组分为小于pivot和大于pivot两部分,递归排序。

版本一:三数取中 + 双指针扫描(完整版)


public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    // 三数取中法选pivot(避免最坏情况)
    int mid = left + (right - left) / 2;
    if (arr[left] > arr[mid]) swap(arr, left, mid);
    if (arr[left] > arr[right]) swap(arr, left, right);
    if (arr[mid] > arr[right]) swap(arr, mid, right);
    swap(arr, mid, right - 1);  // pivot放到right-1位置

    int pivot = arr[right - 1];
    int i = left, j = right - 1;

    while (true) {
        while (arr[++i] < pivot);  // 从左找>=pivot的
        while (arr[--j] > pivot);  // 从右找<=pivot的
        if (i >= j) break;
        swap(arr, i, j);
    }
    swap(arr, i, right - 1);  // pivot归位

    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

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

版本二:简洁版(面试推荐,5分钟写完)


public static void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, hi);
    quickSort(arr, lo, i - 1);
    quickSort(arr, i + 1, hi);
}

版本三:随机pivot + 三路分区(生产级,解决大量重复元素)


import java.util.Random;

public class QuickSort3Way {

    private static final Random RNG = new Random();

    public static void sort(int[] arr) {
        shuffle(arr);  // 随机打乱,消除输入依赖
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;

        // --- 小数组切换插入排序(优化递归开销)---
        if (hi - lo + 1 < 16) {
            insertSort(arr, lo, hi);
            return;
        }

        // --- 三路分区:Dijkstra荷兰国旗 ---
        int pivot = arr[lo];
        int lt = lo;       // [lo..lt-1] < pivot
        int gt = hi;       // [gt+1..hi] > pivot
        int i  = lo + 1;   // [lt..i-1] == pivot

        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt++, i++);
            } else if (arr[i] > pivot) {
                swap(arr, i, gt--);
            } else {
                i++;
            }
        }
        // 现在:arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot

        sort(arr, lo, lt - 1);
        sort(arr, gt + 1, hi);
    }

    // --- 辅助方法 ---
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }

    private static void shuffle(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            int j = RNG.nextInt(i + 1);
            swap(arr, i, j);
        }
    }

    private static void insertSort(int[] arr, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= lo && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

三路分区的关键: 大量重复元素时,等于pivot的区间被整体跳过,不再递归。极端情况(全部相同元素)一次partition就结束,复杂度退化为O(n)。

面试话术: "快排平均O(nlogn),最坏O(n^2)(已排序数组)。三数取中法选pivot可避免最坏情况,三路分区可解决大量重复元素退化。不稳定(交换可能改变相等元素的相对顺序)。Java的Arrays.sort()对基本类型用双轴快排(DualPivotQuicksort)。"


相关页面