Question

使用链表的时候归并排序和插入排序的区别是什么?

使用链表的时候归并排序和插入排序的区别是什么? 比如说9、1、2、3这个序列归并排序，先取9生成子序列A，然后再取1生成序列B，B和A按照归并操作的原理，A中的1进入序列C，然后把B复制到C后面，可是我感觉，这个和直接插到A后面没有区别啊。。。归并排序和插入排序区别是什么?

Answer 1

从本质上讲，所有的排序都没有区别，无外乎是“比较”、“移动”。
你所说的归并排序是“2-路归并排序”，初始得到4个有序序列:9、1、2、3;第一趟分别对9和1、2和3进行两两归并，得到1、9、2、3;第二趟对1、9和2、3两个有序子序列进行两两归并，得到1、2、3、9。
归并排序操作本质上还是先比较，再插入。它的时间复杂度是O(nlogn)。
你所说的插入排序是“直接插入排序”，初始得到1个有序序列:9;第一趟将1插入到初始有序序列中，得到1、9;第二趟将2插入到有序序列1、9中，得1、2、9;第三趟将3插入到有序序列1、2、9中，得到1、2、3、9。
直接插入操作本质是也是先比较，再插入。它的时间复杂度是O(n*n)。
如果一定要说两者的区别，归并排序是将一段有序记录插入到另一段有序记录中，插入排序是将一个记录插入到一段有序记录中。