如何使Java实现的快速排序（Quicksort）算法稳定？技术求助

普通原地快速排序无法保持稳定性的核心原因是：分区过程中的交换操作会打乱相等元素的相对位置。比如当pivot是某个相等元素时，交换可能导致原本在前面的相等元素被移到后面，破坏相对顺序。

要实现稳定的快速排序，我们可以通过额外空间分区的方式，将数组拆分为小于、等于、大于pivot的三个部分，保留等于pivot元素的原始顺序，再合并后递归排序左右部分。以下是具体实现：

@Override
public void quickSortStable(Integer[] data) {
    if (data == null || data.length <= 1) {
        return;
    }
    quickSortStable(data, 0, data.length - 1);
}

private static void quickSortStable(Integer[] data, int start, int end) {
    if (start >= end) {
        return;
    }
    // 分区后得到等于pivot元素的左右边界
    int[] bounds = partitionStable(data, start, end);
    // 递归排序小于pivot的区域和大于pivot的区域
    quickSortStable(data, start, bounds[0] - 1);
    quickSortStable(data, bounds[1] + 1, end);
}

private static int[] partitionStable(Integer[] data, int start, int end) {
    int pivot = data[end];
    // 分别存放小于、等于、大于pivot的元素，保留原始顺序
    List<Integer> less = new ArrayList<>();
    List<Integer> equal = new ArrayList<>();
    List<Integer> greater = new ArrayList<>();

    for (int i = start; i <= end; i++) {
        if (data[i] < pivot) {
            less.add(data[i]);
        } else if (data[i] == pivot) {
            equal.add(data[i]);
        } else {
            greater.add(data[i]);
        }
    }

    // 将元素放回原数组
    int index = start;
    for (int num : less) {
        data[index++] = num;
    }
    int leftEqualBound = index;
    for (int num : equal) {
        data[index++] = num;
    }
    int rightEqualBound = index - 1;
    for (int num : greater) {
        data[index++] = num;
    }

    return new int[]{leftEqualBound, rightEqualBound};
}

关键说明 #

• 稳定性保证：遍历原数组时，等于pivot的元素会按原始出现顺序加入equal列表，再写回原数组，因此相等元素的相对顺序完全保留。
• 空间代价：这种实现需要O(n)的额外空间来存放三个子列表，这是实现稳定快速排序的必要权衡——原地交换的快速排序无法避免相等元素的顺序打乱。

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