java - 使用插入排序只对数组的一部分进行排序

Question

我正在编写一个快速排序程序。部分快速排序涉及使用插入排序，但它只对特定范围的元素进行排序，因为快速排序会处理其余部分。我正在尝试模拟我的教科书提供的一种方法，该方法使用

   public static void insertionSort(int a[], int left, int right)

但我正在努力弄清楚左右是如何使用的。下面是不使用参数 left 和 right 的插入排序代码:

public static void insertionSort(int a[], int left, int right) {
    int j;
    for (int p = 1; p < a.length; p++) {
        int tmp = a[p];
        for(j = p; j > 0 && tmp < a[j - 1]; j--) {
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}

如果我要添加左右参数来帮助仅对数组的一部分进行排序，它们将应用于何处？

感谢您的帮助。

Answer 1

在 for 循环声明中使用 left 和 right:

public static void insertionSort(int a[], int left, int right) {
    int j;
    for (int p = left; p < right; p++) {
        int tmp = a[p];
        for(j = p; j > 0 && tmp < a[j - 1]; j--) {
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}

示例输入:insertionSort({3, 2, 6, 5, 8, 3, 6, 7, 0}, 2, 6)

示例输出:{3, 2, 3, 5, 6, 8, 6, 7, 0}

编辑:

在上面的例子中，左边是包容性的，右边是排他性的。如果要包含正确的索引，请将 p < right 更改为 p<= right。调用索引从 0 开始的方法时请记住。