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 - 二进制插入排序，排除故障

回答

相关问题