为何我实现的Java迭代版Quick Sort运行速度极慢？

你的迭代版快速排序性能差，主要有以下几个核心问题：

1. 固定选择末尾元素作为pivot，易触发最坏情况 #

你在分区时始终用arr[end]作为基准值，当数组已经有序、接近有序，或者存在大量重复元素时，分区会极度不平衡，时间复杂度直接退化为O(n²)，这是性能暴跌的最主要原因。

2. 栈的处理顺序未优化，缓存命中率低 #

你当前的逻辑是先将左子区间入栈，再入右子区间，没有做小区间优先处理。快速排序处理小的子数组时，数据更易被CPU缓存命中，先处理小范围数据能大幅提升缓存利用率，而当前顺序会降低局部性，拖慢执行速度。同时你创建了长度等于数组大小的栈，完全没必要——快速排序的栈深度平均仅为O(log n)，过大的栈会浪费内存（虽不是核心性能问题，但属于冗余设计）。

3. 分区函数存在无意义交换 #

在分区循环中，当i == countIndex时，你依然会执行一次自己和自己的交换，这会产生不必要的函数调用和内存操作，累积起来会影响性能。

4. 未针对小数据量切换更高效的排序算法 #

快速排序的常数项开销（分区、栈操作）在处理极小的子数组（比如长度<20）时，反而不如插入排序高效。强行用快速排序处理这类数据，会增加额外开销。

优化后的代码示例 #

优化点说明：

• 用三数取中法选择pivot，避免最坏情况
• 栈处理时优先压入大区间，再压入小区间，保证先处理小范围数据
• 分区时跳过自身交换，减少冗余操作
• 子数组长度小于16时，切换为插入排序

public static void quickSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    // 栈深度最多为log2(2^31)≈31，所以32长度足够
    int[] stackArr = new int[32];
    int count = -1;

    stackArr[++count] = 0;
    stackArr[++count] = arr.length - 1;

    while (count >= 0) {
        int end = stackArr[count--];
        int start = stackArr[count--];

        // 小数据量切换插入排序
        if (end - start <= 15) {
            insertionSort(arr, start, end);
            continue;
        }

        int pivot = partition(arr, start, end);

        // 先压大区间，再压小区间，保证栈顶是小区间优先处理
        if (pivot - 1 - start > end - (pivot + 1)) {
            stackArr[++count] = start;
            stackArr[++count] = pivot - 1;
            stackArr[++count] = pivot + 1;
            stackArr[++count] = end;
        } else {
            stackArr[++count] = pivot + 1;
            stackArr[++count] = end;
            stackArr[++count] = start;
            stackArr[++count] = pivot - 1;
        }
    }
}

public static int partition(int[] arr, int start, int end) {
    // 三数取中法选择pivot，避免最坏情况
    int mid = start + (end - start) / 2;
    if (arr[mid] > arr[end]) swap(arr, mid, end);
    if (arr[start] > arr[end]) swap(arr, start, end);
    if (arr[mid] > arr[start]) swap(arr, mid, start);
    // 将选中的pivot移到end位置
    swap(arr, start, end);
    int pivotVal = arr[end];

    int countIndex = start;
    for (int i = start; i < end; i++) {
        if (arr[i] <= pivotVal) {
            // 跳过自身交换，减少冗余操作
            if (i != countIndex) {
                swap(arr, i, countIndex);
            }
            countIndex++;
        }
    }
    swap(arr, countIndex, end);
    return countIndex;
}

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

// 插入排序辅助函数，处理小数据量更高效
public static void insertionSort(int[] arr, int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= start && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

内容的提问来源于stack exchange，提问作者Sertan Orenay