使用中位数 3 的快速排序中的逻辑错误

Question

该指令是将快速排序程序编辑为 select 三的中位数作为基准而不是数组的第一个值。

为此，我对代码进行了如下编辑：

public class medianOf3 {

        //Main method and test array 
        public static void main(String[] args) {

            int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
            quickSort(list);
            for (int i = 0; i < list.length; i++)
                System.out.print(list[i] + " ");
            System.out.println();
        }

        public static void quickSort(int[] list) {
            quickSort(list, 0, list.length - 1);
        }
        //The quicksort method 
        public static void quickSort(int[] list, int first, int last) {
            if (last > first) {
                int pivotIndex = partition(list, first, last);
                quickSort(list, first, pivotIndex - 1);
                quickSort(list, pivotIndex + 1, last);
            }
        }

       // Returns the median of three integers 
        public static int median(int first, int middle, int last) {
            return Math.max(Math.min(first, middle), Math.min(Math.max(first, middle), last));
        }

        //returns the index of a value 
        public static int  findIndex (int[] list, int t) { 
            if (list == null) return -1;
            int len = list.length;
            int i = 0;
            while (i < len) {
                if (list[i] == t) return i;
                else i=i+1;
            }
            return -1;
        }

    public static int partition(int[] list, int first, int last) {

        int middle = ((last-first) / 2)+first;    
        int pivot = median(list[first], list[middle], list[last]); // selecting the median of three (of the first, middle and last value) as the pivot
        int low = first +1; // Index for forward search
        int high = last; // Index for backward search
        int index = findIndex(list, pivot );

        int swap = list[index];
        list[index] = list[0];
        list[0] = swap;

        while (high > low) {

            // Search forward from left
            while (low <= high && list[low] <= pivot)
            low++;
            // Search backward from right
            while (low <= high && list[high] > pivot)
            high--;
            // Swap two elements in the list
                if (high > low) {
                int temp = list[high];
                list[high] = list[low];
                list[low] = temp;
                }
            }

        while (high > first && list[high] >= pivot)
        high--;

        // Swap pivot with list[high]

        if (pivot > list[high]) {
            list[first] = list[high];
            list[high] = pivot;
            return high;
        } else { return first;}
        }  

}

以上代码returns输出如下：

14 1 2 2 3 3 5 6 12 14

期望的输出是这样的：

-2 1 2 2 3 3 5 6 12 14

使用调试器，我能够在一次计算中正确排序数组，只有最后 2 个值需要交换：

-2 1 2 2 3 3 5 6 14 12

最终流通处在

list[index] = list[0];

partition方法的那一行，是错误发生的地方，使用了debugger。我觉得这很可能是一个逻辑错误，但我不确定此时到底出了什么问题。

感谢所有反馈。

Answer 1

我建议作为解决方案（基于您的代码并进行少量更改）：

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(2, 3, 2, 5, 6, 1, -2, 3, 14, 12);
    quickSort(list, 0, list.size() - 1);
    System.out.println(list);
}

private static void quickSort(List<Integer> list, int first, int last) {
    if (last - first > 0) {
        int pivot = pivot(list, first, last);
        int index = partition(list, first, last, pivot);
        quickSort(list, first, index - 1);
        quickSort(list, index + 1, last);
    }
}

private static int pivot(List<Integer> list, int first, int last) {
    return ((last - first) / 2) + first;
}

private static int partition(List<Integer> list, int first, int last, int pivot) {
    Collections.swap(list, last, pivot);
    int j = first;
    for (int i = first; i < last; i++) {
        if (list.get(i) <= list.get(last)) {
            Collections.swap(list, i, j);
            j++;
        }
    }
    Collections.swap(list, last, j);
    return j;
}

Answer 2

具有单个函数和防止堆栈溢出的替代示例（最坏情况下的时间复杂度仍然是 O(n^2)）。在此示例中，3 的中位数是通过对 a[lo, md, hi] 进行排序来执行的，其中 md = (lo+hi)/2，这需要 3 if/swaps.

    @SuppressWarnings("empty-statement")
    public static void qsort(int[] a, int lo, int hi)
    {
        while(lo < hi){
            int  md = lo+(hi-lo)/2;
            int  ll = lo-1;
            int  hh = hi+1;
            int t;
            if(a[lo] >  a[hi]){         // median of 3
                t     = a[lo];
                a[lo] = a[hi];
                a[hi] = t;
            }
            if(a[lo] >  a[md]){
                t     = a[lo];
                a[lo] = a[md];
                a[md] = t;
            }
            if(a[md] >  a[hi]){
                t     = a[md];
                a[md] = a[hi];
                a[hi] = t;
            }
            int p = a[md];
            while(true){                // partition
                while(a[++ll] < p);
                while(a[--hh] > p);
                if(ll >= hh)
                    break;
                t     = a[ll];
                a[ll] = a[hh];
                a[hh] = t;
            }
            ll = hh++;
            // recurse on smaller part, loop on larger part
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }

使用中位数 3 的快速排序中的逻辑错误

Logical error in a quicksort using a median of 3

java

quicksort

median