使用插入排序仅对数组的一部分进行排序

Question

我正在编写一个快速排序程序。部分quicksort涉及使用insertionsort，但它只对一定范围内的元素进行排序，因为quicksort处理其余部分。我试图模仿我的教科书提供的方法，使用

public static void insertionSort(int a[], int left, int 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循环的声明：

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; 
    } 
} 

例如输入：插入排序（{3,2，6，5,8，3，6，7，0}，2，6）

输出示例：{3，2，3，5，6，8，6，7，0}

编辑：

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