排序完整集合与二进制插入排序到新集合

Question

什么是平均速度更快（忽略最佳情况）：

int[] arr = new arr[]{1,10,4,3,20,9};
Arrays.sort(arr);

VS 二进制插入排序到一个新数组（更高 space 复杂度）

int[] arr =  new arr[]{1,10,4,3,20,9};
int[] arr2 = new arr2[arr.length];

for (int i=0; i<arr.length; i++){
    arr2[i] = insertionSort(arr2, 0, arr2.length, arr[i]);
}

public void insertionSort(int[] arr2, int min, int max, int val){
     // perform binary search insertion...
}

还是它们是同一回事？

选项 1：假设我们使用平均为 (nlog(n)) 的排序方法选项 2：新数组的插入排序也将是 n*log(n) 但是，我认为更快，因为 log(n) 从 log(1) -> log(n) 开始，因为它填满了数组（不是像选项 1)

中那样的平面 log(n)

想法？

Answer 1

二分插入排序采用二分查找来确定插入新元素的正确位置，因此在最坏情况下进行⌈log2 n⌉次比较，即O(n log n).

The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.

其中 Arrays.sort(arr); 使用双 主元快速排序时间复杂度
双主元快速排序比原来的单主元快速排序快一点。 ...但是，当数组已经按升序或降序排序时，最坏的情况仍将是 O(n^2)。

因此在大多数情况下 Arrays.sort(arr) 更好。

排序完整集合与二进制插入排序到新集合

Sorting full collection vs Binary Insertion sorting into a new collection

java

sorting

time-complexity