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

问题根源 #

你的代码中快速排序调用插入排序时的参数范围不匹配：

• 快速排序的quickSort方法里，last参数代表子数组的最后一个元素的索引（比如初始调用传入v.length-1）。
• 但InsertionSort.insertionSort方法的循环条件是i < last，这意味着它只会处理到索引last-1的元素，完全漏掉了索引last的元素。未被处理的元素留在原位置，最终导致整体排序结果混乱。

修复方案 #

以下两种方案任选其一即可：

方案1：修改插入排序的循环范围

调整InsertionSort中insertionSort方法的循环条件，让它覆盖到last索引的元素：

public class InsertionSort {
    public void insertionSort(int [] arr, int first, int last){
        // 把i < last 修改为 i <= 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 - 1); // 同步修改为v.length-1，保持逻辑一致
    }
}

方案2：修改快速排序调用插入排序的参数

保持InsertionSort不变，在快速排序中调用插入排序时，把last参数改为last+1，匹配插入排序的范围定义：

private void quickSort(int [] array, int first, int last){
 if(first < last){
    if ((last - first) < 10){
        // 传入last+1，让插入排序覆盖到last索引的元素
        insert.insertionSort(array, first, last + 1);
    }
    else {
        int pivot = partition(array, first, last);
        quickSort(array, first, pivot - 1);
        quickSort(array, pivot + 1, last);
    }
 }
}

验证效果 #

修复后，测试你给出的示例数组：

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, 53, 75, 124, 234, 242, 332, 646, 3563, 4646]

内容的提问来源于stack exchange，提问作者User