每日算法 — 使用java实现Introsort：内省排序与快速堆排序自适应混合策略

算法概述

Introsort（Introspective Sort，内省排序）是由 David Musser 于 1997 年设计的混合排序算法，旨在结合快速排序的平均高效性和堆排序的最坏情况保证。它被设计为 C++ STL std::sort 的底层实现，也被广泛应用于需要稳定最坏性能的系统级排序。

Introsort 的核心思想是：以快速排序为主体，但监控递归深度；当递归深度超过阈值（通常为 2×log₂n）时，切换到堆排序以避免快速排序的最坏 O(n²) 情况；对于极小的子数组（通常 ≤16 个元素），则使用插入排序提升常数效率。

核心原理

1. 快速排序分区：选取枢轴（pivot），将数组分为小于和大于枢轴的两部分。
2. 递归深度限制：记录当前递归深度，若超过 2 × floor(log₂n) 则切换到堆排序。
3. 三数取中法：选取首、中、尾三个元素的中位数作为枢轴，避免极端划分。
4. 小规模优化：当子数组长度 ≤16 时，使用插入排序而非继续递归。
5. 堆排序兜底：在最坏情况下保证 O(n log n) 的时间复杂度。

Java 实现

import java.util.Arrays;

/**
 * Introsort 内省排序实现
 * 时间复杂度：最坏 O(n log n)，平均 O(n log n)
 * 空间复杂度：O(log n) 递归栈
 * 非稳定排序
 */
public class IntroSort {
    // 小规模阈值，低于此值使用插入排序
    private static final int INSERTION_THRESHOLD = 16;

    /**
     * 对 Comparable 数组进行 Introsort 排序
     */
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        if (arr == null || arr.length < 2) return;
        int maxDepth = 2 * floorLog2(arr.length);
        introSort(arr, 0, arr.length - 1, maxDepth);
    }

    /**
     * Introsort 主递归函数
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static <T extends Comparable<? super T>> void introSort(T[] arr, int lo, int hi, int depthLimit) {
        while (hi - lo > INSERTION_THRESHOLD) {
            if (depthLimit == 0) {
                // 递归深度超限，切换到堆排序
                heapSort(arr, lo, hi);
                return;
            }
            depthLimit--;

            // 三数取中作为枢轴，并放置到 hi-1 位置
            int mid = lo + (hi - lo) / 2;
            medianOfThree(arr, lo, mid, hi);

            // 分区
            int p = partition(arr, lo, hi);
            // 递归排序较大的一半，对较小的一半继续循环（减少递归深度）
            if (p - lo < hi - p) {
                introSort(arr, lo, p - 1, depthLimit);
                lo = p + 1;
            } else {
                introSort(arr, p + 1, hi, depthLimit);
                hi = p - 1;
            }
        }

        // 最后使用插入排序处理小范围
        insertionSort(arr, lo, hi);
    }

    /**
     * 三数取中：将 lo, mid, hi 三个位置的中位数交换到 hi 位置
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static <T extends Comparable<? super T>> void medianOfThree(T[] arr, int lo, int mid, int hi) {
        if (((Comparable) arr[mid]).compareTo(arr[lo]) < 0) {
            swap(arr, lo, mid);
        }
        if (((Comparable) arr[hi]).compareTo(arr[lo]) < 0) {
            swap(arr, lo, hi);
        }
        if (((Comparable) arr[hi]).compareTo(arr[mid]) < 0) {
            swap(arr, mid, hi);
        }
        // 将中位数放到 hi-1 位置作为枢轴
        swap(arr, mid, hi - 1);
    }

    /**
     * Hoare 分区方案（三数取中后，枢轴在 hi-1）
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static <T extends Comparable<? super T>> int partition(T[] arr, int lo, int hi) {
        T pivot = arr[hi - 1];
        int i = lo;
        int j = hi - 1;

        while (true) {
            while (((Comparable) arr[++i]).compareTo(pivot) < 0) {
                // 从左向右找大于等于 pivot 的元素
            }
            while (((Comparable) arr[--j]).compareTo(pivot) > 0) {
                // 从右向左找小于等于 pivot 的元素
            }
            if (i >= j) break;
            swap(arr, i, j);
        }
        // 将枢轴放到正确位置
        swap(arr, i, hi - 1);
        return i;
    }

    /**
     * 插入排序，处理小范围数组
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static <T extends Comparable<? super T>> void insertionSort(T[] arr, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            T key = arr[i];
            int j = i - 1;
            while (j >= lo && ((Comparable) arr[j]).compareTo(key) > 0) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    /**
     * 堆排序，用于递归深度超限时的兜底
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static <T extends Comparable<? super T>> void heapSort(T[] arr, int lo, int hi) {
        int n = hi - lo + 1;
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, lo, n, i);
        }
        // 逐个提取最大元素
        for (int i = n - 1; i > 0; i--) {
            swap(arr, lo, lo + i);
            siftDown(arr, lo, i, 0);
        }
    }

    /**
     * 堆的下沉操作
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static <T extends Comparable<? super T>> void siftDown(T[] arr, int offset, int size, int root) {
        T element = arr[offset + root];
        int child;
        while ((child = 2 * root + 1) < size) {
            // 选择较大的子节点
            if (child + 1 < size && ((Comparable) arr[offset + child]).compareTo(arr[offset + child + 1]) < 0) {
                child++;
            }
            if (((Comparable) element).compareTo(arr[offset + child]) >= 0) break;
            arr[offset + root] = arr[offset + child];
            root = child;
        }
        arr[offset + root] = element;
    }

    /**
     * 交换数组中两个元素
     */
    private static <T> void swap(T[] arr, int i, int j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 计算 floor(log2(n))
     */
    private static int floorLog2(int n) {
        int log = 0;
        while (n > 1) {
            n >>= 1;
            log++;
        }
        return log;
    }

    // ==================== 测试入口 ====================
    public static void main(String[] args) {
        // 测试 1：随机数组
        Integer[] arr1 = new Integer[100000];
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = (int) (Math.random() * 1000000);
        }
        IntroSort.sort(arr1);
        System.out.println("随机数组排序: " + (isSorted(arr1) ? "正确" : "错误"));

        // 测试 2：已排序数组（快速排序最坏情况）
        Integer[] arr2 = new Integer[100000];
        for (int i = 0; i < arr2.length; i++) arr2[i] = i;
        IntroSort.sort(arr2);
        System.out.println("已排序数组排序: " + (isSorted(arr2) ? "正确" : "错误"));

        // 测试 3：逆序数组
        Integer[] arr3 = new Integer[100000];
        for (int i = 0; i < arr3.length; i++) arr3[i] = arr3.length - i;
        IntroSort.sort(arr3);
        System.out.println("逆序数组排序: " + (isSorted(arr3) ? "正确" : "错误"));

        // 测试 4：大量重复元素
        Integer[] arr4 = new Integer[100000];
        for (int i = 0; i < arr4.length; i++) arr4[i] = i % 10;
        IntroSort.sort(arr4);
        System.out.println("重复元素排序: " + (isSorted(arr4) ? "正确" : "错误"));

        // 性能对比
        long start = System.currentTimeMillis();
        for (int t = 0; t < 10; t++) {
            Integer[] test = new Integer[50000];
            for (int i = 0; i < test.length; i++) test[i] = (int) (Math.random() * 1000000);
            IntroSort.sort(test);
        }
        System.out.println("10 次 5万规模排序耗时: " + (System.currentTimeMillis() - start) + "ms");
    }

    private static <T extends Comparable<? super T>> boolean isSorted(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].compareTo(arr[i - 1]) < 0) return false;
        }
        return true;
    }
}

复杂度分析

Introsort 是非稳定排序。相比纯快速排序，它消除了最坏 O(n²) 的风险；相比纯堆排序，它保留了快速排序在平均情况下的缓存友好性。

适用场景

• 需要最坏情况性能保证的大规模排序
• C++ STL std::sort 风格的高性能通用排序
• 对快速排序最坏情况敏感的安全关键系统
• 基本类型数组的高效原地排序