Java - 二進制插入排序，排除故障

我有一個任務，我需要使用二進制插入排序排序數組。這是我想出了一個解決方案，但實在是太慢了：Java - 二進制插入排序，排除故障

public static void binaryInsertionSort(int[] a) { 
    int ins, i, j; 
    int tmp; 
    for (i = 1; i < a.length; i++) { 
     ins = BinarySearch (a, 0, i, a[i]); 
      if(ins < i) { 
       tmp = a[i]; 
       for (j = i - 1; j >= ins; j--) 
        a[j+1] = a[j]; 
       a[ins] = tmp; 
      } 
    } 
} 

private static int BinarySearch(int[] a, int low, int high, int key) { 

    int mid; 
    if (low == high) 
     return low; 
    mid = low + ((high - low)/2); 
    if (key > a[mid]) 
     return BinarySearch (a, mid + 1, high, key); 
    else if (key < a[mid]) 
     return BinarySearch (a, low, mid, key); 
    return mid; 

}

我被推薦使用，我已經試過System.arraycopy方法，但我不明白爲什麼它不工作：

public static void binaryInsertionSort(int[] a) { 
    int ins, i; 
    int tmp = a[i]; 
    for (i = 1; i < a.length; i++) { 
     ins = binarySearch (a, 0, i, a[i]); 
      if(ins < i){ 
       System.arraycopy(a, ins, a, ins + 1, i - ins); 
       a[ins] = tmp; 
      } 
    } 
} 

private static int binarySearch(int[] a, int low, int high, int key) { 
    int mid; 
    if (low == high) 
     return low; 
    mid = low + ((high - low)/2); 
    if (key > a[mid]) 
     return binarySearch (a, mid + 1, high, key); 
    else if (key < a[mid]) 
     return binarySearch (a, low, mid, key); 
    return mid; 
}

任何幫助是有幫助的。

來源

2017-02-19 elMatador

說明什麼，當你**運行情況**你的代碼把一個**滿。 ** [mcve]向我們展示了您使用的數據以及預期/實際結果的外觀 – GhostCat

您第一次編寫的原始代碼對我來說看起來沒問題，我不確定它的含義太慢了。二進制插入排序最終會花費O（n^2）時間複雜度。您的問題是關於如何快速製作或製作第二個實施工作？即使你使用system.arraycopy使你的第二個實現工作，我也不相信它會讓你的程序運行速度非常快。對於快速運行的排序算法，請使用O（nlogn）算法之一。 –

我的問題是關於使第二個代碼工作。是的，儘管初始代碼有效，但System.arraycopy方法比原始代碼快大約4倍）） – elMatador

那麼，在此期間，答案比我想象的要容易。我在錯誤的地方初始化了局部變量。相反的：

正確的方法是：

public static void binaryInsertionSort(int[] a) { 
    int ins, i; 
     for (i = 1; i < a.length; i++) { 
      **int tmp = a[i];** 
      ins = binarySearch (a, 0, i, a[i]); 
       if(ins < i){ 
        System.arraycopy(a, ins, a, ins + 1, i - ins); 
        a[ins] = tmp; 
       } 
    } 
}

和它的作品（：

來源

2017-02-19 11:46:21 elMatador

Java - 二進制插入排序，排除故障

回答

相關問題