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

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[] ={1, 13日,53岁,3646年,75年,4646年,332年,2124年,3563年,242234年,35岁的2 1};

这是打印的排序版本:

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

有人能帮我解决这个问题吗?我检查过我的插入法和快速排序算法(划分法)的工作原理很好，所以问题一定在快速排序的某个地方方法。顺便说一句，我看到过一些关于堆栈溢出的类似帖子，但没有在我的案例中，他们都起了作用。我在那里尝试的一个技巧效果更好但这并不始终如一。就像说到偶数&奇怪的数组,当使用随机数据时，有时有效，有时无效。

谢谢先!

Answer 1

这是一个经典的:off -by- 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参数意味着两个不同的东西!在快速排序的情况下，它是最后一个要排序的元素的索引，在InsertionSort的情况下，它是最后一个要排序的元素的索引。

现在看看当QuickSort调用InsertionSort:

时会发生什么

insert.insertionSort(array, first, last);

您需要从一种约定转换到另一种约定，所以最后一个参数需要是last+1。