为什么我的快速排序和插入排序混合算法不能正常工作？

Question

public class QuicksortFixedPivotInsertion implements IntSorter{
    InsertionSort insert = new InsertionSort();

    public int partition(int [] array, int first, int last){
        int middle = (first+last)/2;   
        swap(array, middle, last);        
        int pivot = array[last];
        int i = first-1;

        for (int j = first; j < last; j++){
            if (array[j]<pivot){
                i++;
                swap(array, i, j);               
    
            }
        } 
        swap(array, i+1, last);
        return i+1;
    }

    private void quickSort(int [] array, int first, int last){
     if(first < last){
        if ((last - first) < 10){
            insert.insertionSort(array, first, last);
        }
        else {
            int pivot = partition(array, first, last);
            quickSort(array, first, pivot - 1);
            quickSort(array, pivot + 1, last);
        }
     }
    }

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

  
    public void sort(int [] v){
        quickSort(v, 0, v.length - 1);
    }
}

这是用于此的插入方法

public class InsertionSort {

    public void insertionSort(int [] arr, int first, int last){
        for(int i = first + 1; i<last ; i++){
            int temp;
            int j = i;
            while(j > first && arr[j-1] > arr[j]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;

            }
        } 
    }

    public void sort(int[] v){
        insertionSort(v, 0, v.length);

    }

所以问题是它不能正常工作，就像我尝试的时候一样 具有不同大小和不同类型数据的数组（已排序 数组，随机数组，随机）它并不总是有效。凭它不 工作，我的意思是它没有正确排序数组。例如它 不对打乱的或随机的数组进行排序。这是一个例子：

int[] a ={1,13,53,3,646,75,4,4646,332,2,124,3563,242,234,35,2,1};

这是打印出来的排序版本：

[1, 1, 2, 2, 3, 4, 13, 35, 75, 124, 234, 242, 53, 332, 3563, 4646, 646]

有人可以帮我解决这个问题吗？我检查过我的 插入法和快速排序算法（分区法）有效 非常好，所以问题必须在快速排序中的某个地方 方法。顺便说一句，我在堆栈溢出上看到了一些类似的帖子，但没有 他们中的一个在我的案例中起作用。我在那里尝试过的一个技巧效果更好 但它并不一致。就偶数和奇数数组而言， 在使用随机数据时有时有效，有时无效。

提前致谢！

Answer 1

这是一个经典：差一个错误。让我们看看你的两个分类器类：

public class QuicksortFixedPivotInsertion implements IntSorter{
    /* ... */
    private void quickSort(int [] array, int first, int last){
        /* ... */
    }
  
    public void sort(int [] v){
        quickSort(v, 0, v.length - 1);
    }
}

public class InsertionSort {

    public void insertionSort(int [] arr, int first, int last){
        /* ... */
    }

    public void sort(int[] v){
        insertionSort(v, 0, v.length);
    }
}

看到区别了吗？那个

-1

？那不是错误所在，但这给了我们一个提示，这里出了什么问题：您的

last

参数意味着两个不同的东西！在 QuickSort 的情况下，它是最后一个要排序的元素的索引，在 InsertionSort 的情况下，它是 one past 最后一个要排序的元素。

现在看看当 QuickSort 调用 InsertionSort 时会发生什么：

            insert.insertionSort(array, first, last);

您需要将一种约定转换为另一种约定，因此最后一个参数需要是

last+1

.