排序全相等整数数组时出现Stack overflow错误

我尝试对一个包含100000个全相等元素的数组进行排序，使用的快速排序代码如下：

public static void quickSortFirst(int[] arr, int left, int right) {
    if (left < right) {
      int pivotIndex = partition(arr, left, right);
      quickSortFirst(arr, left, pivotIndex - 1);
      quickSortFirst(arr, pivotIndex + 1, right);
    }
  }

  private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
      while (i <= j && arr[i] <= pivot) {
        i++;
      }
      while (i <= j && arr[j] > pivot) {
        j--;
      }
      if (i <= j) {
        swap(arr, i, j);
      }
    }
    swap(arr, left, j);
    return j;
  }

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

这段代码在排序1000和10000个元素时正常，但元素数量增至100000时会触发Stack overflow错误。我试过网上多种快速排序实现，只要处理100000个全相等元素都会出现这个问题。

问题根源 #

核心问题在于固定选第一个元素当基准 + 全相等元素的极端场景：
当所有元素都等于基准值时，partition方法会把所有元素都分到基准的同一侧——arr[i] <= pivot会让i一直走到right位置，最后j停在left处，交换后返回的pivotIndex就是left。这导致每次递归只会把右区间缩小1，左区间完全没变化，递归深度直接拉到O(n)级别。100000的递归深度远远超过JVM默认的栈容量（通常只有几千到几万），自然触发栈溢出。

解决方案 #

1. 优化基准值选择

别每次固定选第一个元素当基准，改用三数取中法（取左、中、右三个位置的元素，选中间值当基准）或者随机选基准，这样能让全相等元素场景下的partition结果尽量均分左右区间，把递归深度降到O(logn)。

示例（三数取中优化partition）：

private static int partition(int[] arr, int left, int right) {
    // 三数取中选基准，避免固定选左边界的问题
    int mid = left + (right - left) / 2;
    // 调整左、中、右位置的元素，让中间值移到左边界
    if (arr[mid] < arr[left]) swap(arr, left, mid);
    if (arr[right] < arr[left]) swap(arr, left, right);
    if (arr[right] < arr[mid]) swap(arr, mid, right);
    swap(arr, left, mid);

    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
        }
    }
    swap(arr, left, j);
    return j;
}

2. 尾递归优化

把最后一次递归调用改成循环，减少栈帧的累积。同时优先处理较小的区间，进一步压缩栈深度。

示例（修改quickSortFirst方法）：

public static void quickSortFirst(int[] arr, int left, int right) {
    while (left < right) {
        int pivotIndex = partition(arr, left, right);
        // 优先处理较小的区间，减少栈深度
        if (pivotIndex - left < right - pivotIndex) {
            quickSortFirst(arr, left, pivotIndex - 1);
            left = pivotIndex + 1;
        } else {
            quickSortFirst(arr, pivotIndex + 1, right);
            right = pivotIndex - 1;
        }
    }
}

3. 针对全相等元素的特殊处理

在partition时先检查当前区间是否所有元素都等于基准，是的话直接返回中间位置，避免无效递归。适合明确有大量重复元素的场景。

示例：

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    // 检查当前区间是否全是相等元素
    boolean allEqual = true;
    for (int k = left + 1; k <= right; k++) {
        if (arr[k] != pivot) {
            allEqual = false;
            break;
        }
    }
    if (allEqual) {
        return left + (right - left) / 2; // 返回中间位置，均分区间
    }

    int i = left + 1;
    int j = right;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
        }
    }
    swap(arr, left, j);
    return j;
}

内容的提问来源于stack exchange，提问作者Beren Şenbay