英文:
Sorting full collection vs Binary Insertion sorting into a new collection
问题
int[] arr = new arr[]{1,10,4,3,20,9};
Arrays.sort(arr);
VS
将新数组进行二分插入排序（空间复杂度较高）
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){
// 执行二分搜索插入...
}
或者它们是相同的吗？
选项1：假设我们使用平均为(nlog(n))的排序方法
选项2：对新数组进行插入排序，时间复杂度也是n*log(n)，但我认为会更快，因为log(n)会从log(1)逐渐增加到log(n)，随着数组的填充（不像选项1中的恒定log(n)）
想法？
英文:
What is faster on an average (ignore optimal cases):
int[] arr = new arr[]{1,10,4,3,20,9};
Arrays.sort(arr);
VS Binary insertion sort into a new array (higher space complexity)
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...
}
or are they the same thing?
Option 1: assuming we use sorting method with an average of (nlog(n))
Option 2: the insertion sort into new array will also be n*log(n) as well but, I think faster because the log(n) goes from log(1) -> log(n) as it fills up the array (not a flat log(n) like in option 1)
Thoughts?
答案1
得分: 1
二分插入排序利用二分搜索确定插入新元素的正确位置，因此在最坏情况下执行⌈log2 n⌉次比较，时间复杂度为O(n log n)。
> 整体而言，该算法的平均运行时间仍为O(n2)，因为每次插入都需要一系列的交换操作。
而Arrays.sort(arr);使用双轴快速排序的时间复杂度<br>
双轴快速排序比原始的单轴快速排序稍快。... 但仍然，当数组已按升序或降序排序时，最坏情况时间复杂度将为O(n^2)。
因此在大多数情况下，Arrays.sort(arr)更为优越。
英文:
Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2 n⌉ comparisons in the worst case, which is 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.
where as Arrays.sort(arr); uses dual pivot quicksort time complexity<br>
Dual pivot quick sort is a little bit faster than the original single pivot quicksort. ... But still, the worst case will remain O(n^2) when the array is already sorted in an increasing or decreasing order.
hence Arrays.sort(arr) is better in most of the use case.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论