結合合併排序與插入排序

Question

有人請告知爲什麼此代碼無法正常工作時，閾值設置爲< = 3？數組的最後幾位數未被排序。例如：

輸入：{20,19,18,17，16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1} ;輸出：{3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }

public class mergesorttest{ 
    public static void main(String[]args){ 
     int d[]= {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; 
     mergeSort(d,0,d.length); 
     for(int x:d) System.out.print(x+" "); 
     System.out.println(); 
    } 

    static final int THRESHOLD = 3; 
    static void mergeSort(int f[],int lb, int ub){ 
     if (ub - lb <= THRESHOLD) 
      insertion_srt(f, lb, ub); 
     else 
     { 
      int mid = (lb+ub)/2; 
      mergeSort(f,lb,mid); 
      mergeSort(f,mid,ub); 
      merge(f,lb,mid,ub); 
     } 
    } 

static void merge (int f[],int p, int q, int r){ 
    //p<=q<=r 
    int i =p; int j = q; 
    //use temp array to store merged sub-sequence 
    int temp[] = new int[r-p]; int t = 0; 
    while(i<q && j<r){ 
     if(f[i]<=f[j]){ 
      temp[t] =f[i]; 
      i++;t++; 
     } 
     else{ 
      temp[t] = f[j]; 
      j++; 
      t++; 
     } 

     //tag on remaining sequence 
     while(i<q){ 
      temp[t] = f[i]; 
      i++; 
      t++; 

     } 
     while(j<r){ 
      temp[t]=f[j]; 
      j++; 
      t++; 
     } 
     //copy temp back to f 
     i=p;t=0; 
     while(t<temp.length){ 
      f[i]=temp[t]; 
      i++; 
      t++; 
     } 
     } 
} 

public static void insertion_srt(int array[], int n, int b){ 
     for (int i = 1; i < n; i++){ 
     int j = i; 
     int B = array[i]; 
     while ((j > 0) && (array[j-1] > B)){ 
     array[j] = array[j-1]; 
     j--; 
     } 
     array[j] = B; 
    } 
    } 
} 

P.S. （）也需要一個修復

 while ((j > n) && (array[j-1] > B)){ 

合併，：代碼是從其他崗位 Combining MergeSort with Insertion sort to make it more efficient

Answer 1

在insertion_srt（）借不應該for循環是

for (int i = n+1; i < b; i++){ 

和while循環第一個while循環的尾部大括號需要在代碼之前向上移動以標記其餘序列：

while(i<q && j<r){ 
     if(f[i]<=f[j]){ 
      temp[t] =f[i]; 
      i++; 
      t++; 
     }else{ 
      temp[t] = f[j]; 
      j++; 
      t++; 
     } 
    } 
    while(i<q){ 
     temp[t] = f[i]; 
     i++; 
     t++; 
    } 
    while(j<r){ 
     temp[t]=f[j]; 
     j++; 
     t++; 
    }