如何在不使用java.util包的情况下让快速排序算法稳定？

Question

我在java中实现了快速排序算法，但正在努力使其稳定。 （相等元素的顺序必须保持相同）我不允许使用java库。 （特别是 java.util 包）。

我真的很感激任何进一步的帮助。

这是我当前的代码：

@Override
    public void quickSortStable(Integer[] data) {


        quickSort(data, 0, data.length - 1);

    }

    private static void quickSort(Integer[] data, int start, int end) {

        if (start>= end) return; 

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

        quickSort(data, start, pivot -1); 
        quickSort(data, pivot +1, end); 

    }

    private static int partition(Integer[] data, int start, int end){

        int pivot= data[end]; 
        int i = start -1;

        for (int j = start; j<= end; j++){
            if(data[j]< pivot){
                i++;
                //variable swap i and j
                int temp = data[i];
                data[i]=data[j];
                data[j]= temp;

            }
        }
        
        i++;
        int temp = data[i];
        data[i]=data[end];
        data[end]= temp;

        return i; 

    }

Answer 1

我在java中实现了快速排序算法，但正在努力使其稳定。 （相等元素的顺序必须保持相同）我不允许使用java库。 （特别是 java.util 包）。

如果你想确保你的快速排序算法稳定，你应该保持排序后相等元素的顺序保持不变。

首先，我建议您使用

Integer class

作为对象包装器，而不是

int

作为数组元素的原始类型。这很重要，因为对于原始类型，原始实例最终会被缓存实例更改，从而无法保持稳定性。

其次，修改分区逻辑，将小于或等于主元的元素包含在左侧分区中。这样可以确保与主元具有相同值的元素保持其原始相对顺序。