对于通用排序,答案似乎是否定的,因为快速排序,合并排序和堆排序往往在平均和最差情况下表现更好.但是,插入排序似乎在增量排序方面表现优异,即在保持列表排序的同时,在一段时间内一次向列表添加元素,尤其是在插入排序实现为链接列表时(O(log) n)平均情况与O(n)).但是,堆似乎能够(或几乎)执行增量排序(从堆中添加或删除单个元素具有O(log n)的最坏情况).那么插入排序与其他基于比较的排序算法或堆有什么关系呢？
我已阅读无处不在,对于分而治之的排序算法像Merge-Sort和Quicksort,而不是递归,直到只有一个元素是左,这是更好地转移到Insertion-Sort时候一定阈值,比如30元,达到.那很好,但为什么只有Insertion-Sort？为什么不,Bubble-Sort或Selection-Sort两者都有类似的O(N^2)表现？Insertion-Sort只有当许多元素被预先排序时才应该派上用场(虽然这个优势也应该附带Bubble-Sort),但除此之外,为什么它应该比其他两个元素更有效？
其次,在这个链接中,在第二个答案及其附带的评论中,它表示O(N log N)与O(N^2)最高级别相比表现不佳N.怎么会？N^2应该总是表现得比N log N,因为N > log N对于所有N> = 2,对吧？
已知大小为 n 的数组 A 除了前 k 个元素和最后 k 个元素（其中 k 是常数）外都已排序。以下哪种算法最适合对数组进行排序？
A) Quicksort
B) Bubble sort
C) Selection Sort
D) Insertion Sort
给出的答案是 D。
无法理解这是如何工作的，如果还给出了合并排序，那么答案是什么？
所以我有一个MergeSort算法,我希望将MergeSort与Insertion排序相结合,以减少合并的开销,问题是如何？我想使用插入排序对段进行排序,然后合并.
public class mergesorttest{
public static void main(String[]args){
int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1};
mergeSort(d,0,d.length);
for(int x:d) System.out.print(x+" ");
System.out.println();
}
static void mergeSort(int f[],int lb, int ub){
//termination reached when a segment of size 1 reached -lb+1=ub
if(lb+1<ub){
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 …