如何实现混合快速排序算法

Question

我一直在尝试创建一种混合快速排序算法，第一个元素用作枢轴，当分区大小低于100时，使用插入排序来完成。然后，我必须将执行的比较次数和交换次数与标准的快速排序算法进行比较。我的代码排序似乎有效，但不知何故，当分区大小改变时，比较和交换的数量没有改变。不确定我的代码中的问题到底在哪里。

public class QuickSort100 {
int comparisonCount = 0;
int swapCount = 0;
public void quicksort(int [] array, int lowIndex, int highIndex ) {
if ((lowIndex - highIndex) >= 100){
int index = partition(array, lowIndex, highIndex);
if (lowIndex < index -1){
quicksort(array, lowIndex, index-1);
}
if (index < highIndex){
quicksort(array, index, highIndex);
}
}
else {
insertionSort(array);
}
}
public int [] insertionSort (int[] array) {
int i, j, key, temp;
for (i = 1; i < array.length; i++) {
key = array[i];
j = i - 1;
while (j >= 0 && key < array[j]) {
comparisonCount++;
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
j--;
swapCount++;
}
}
return array;
}

public int partition(int[] array, int lowIndex, int highIndex){
int pivot = array[lowIndex];
int i = lowIndex + 1 ;
for (int j = (lowIndex +1); j < highIndex; j++){
comparisonCount++;

if(array[j] < pivot){
swap(array,i,j);
swapCount++;
i++;
}
}
swap(array, lowIndex, i-1);
swapCount++;
return i;
}

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

Answer 1

您需要修改插入排序以使用lowIndex和highIndex，而不是整个数组。