Quicksort java 前 3 个元素的中位数

Question

我在使用快速排序时遇到问题。我的家庭作业要求我将枢轴设为前 3 个元素的中值，如果列表小于 3，则设为第一个元素。当我这样做时，排序会分崩离析，一些元素会被其他元素覆盖。我不确定我错过了什么，但这是代码：

private static <E extends Comparable<E>> int partition(ArrayList<E> list, int first, int last) {
    ArrayList<E> subList = new ArrayList<E>(list.subList(first, last));
    E pivot = list.get(0);

    int low = first + 1; // Index for forward search
    int high = last; // Index for backward search

    if(list.get(0).getClass().equals(String.class)){
        while (high > low) {
            // Search forward from left
            while (low <= high && list.get(low).toString().compareToIgnoreCase(pivot.toString()) <= 0)
                low++;

            // Search backward from right
            while (low <= high && list.get(high).toString().compareToIgnoreCase(pivot.toString()) > 0)
                high--;

            // Swap two elements in the list
            if (high > low) {
                E temp = list.get(high);
                list.set(high, list.get(low));
                list.set(low, temp);
            }
        }

        while (high > first && list.get(high).toString().compareToIgnoreCase(pivot.toString()) >= 0)
            high--;

        // Swap pivot with list.get(high)
        if (pivot.toString().compareToIgnoreCase(list.get(high).toString()) > 0) {
            list.set(first, list.get(high));
            list.set(high, pivot);
            return high;
        }
        else {
            return first;
        }
    }else{
        //same code, but doesn't convert toString for comparisons
    }
}

当我替换第 3 行时，问题就开始了。

//E pivot = list.get(0);
//change to
E pivot = getPivot(subList);

这是获取数据透视表的代码：

private static <E extends Comparable<E>> E getPivot(ArrayList<E> list){
    if(list.size() < 3){
        return list.get(0);
    }else{
        //sorts ignoring case if the type of data in the list is strings
        if(list.get(0).getClass().equals(String.class)){
            if(list.get(0).toString().compareToIgnoreCase(list.get(1).toString()) > 0){
                if(list.get(0).toString().compareToIgnoreCase(list.get(2).toString()) <= 0){
                    return list.get(0);
                }else if(list.get(1).toString().compareToIgnoreCase(list.get(2).toString()) > 0){
                    return list.get(1);
                }
            }else if(list.get(0).toString().compareToIgnoreCase(list.get(1).toString()) <= 0){
                if(list.get(0).toString().compareToIgnoreCase(list.get(2).toString()) > 0){
                    return list.get(0);
                }else if(list.get(1).toString().compareToIgnoreCase(list.get(2).toString()) <= 0){
                    return list.get(1);
                }
            }
        }else{
            //same code, but doesn't convert toString for comparisons
        }
    }
    return list.get(2);
}

我不太确定从这里到哪里去，我让它工作的唯一方法是 getPivot 方法 returns 每次都是第一个元素，但它没有任何用处。有人能指出我正确的方向吗？谢谢。

Answer 1

就在您 return 之前，当交换将枢轴放在列表的中间时，您错误地假设枢轴始终位于第一个位置。因此，您可能会丢失列表中第一个位置的值，取而代之的是获得主元值的副本。您需要记住在哪个索引处找到了枢轴，并与该索引而不是第一个索引进行交换。

还有一个问题。当您将 low 变量初始化为 first + 1 时，您还假设枢轴位于第一个位置。你不应该在那里加1。否则，您最终可能会在第一个位置得到一个大于 pivot 的值。

Quicksort java 前 3 个元素的中位数

Quicksort java with median of first 3 elements

java

quicksort

median