使用插入排序僅對數組的一部分進行排序

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開始的方法時請記住。