对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
示例 1：
1
2
|
输入: 4->2->1->3
输出: 1->2->3->4
|
示例 2：
1
2
|
输入: -1->5->3->4->0
输出: -1->0->3->4->5
|
看起来很简单的插入排序花了我一晚上.
插入排序不需要多讲，题面总结得很精辟，每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。
但是 链表就不能简单移动了，而是要做到插入（把节点插入相应的地方），遍历找到要插入的地方以后，还要实现交换操作（和数组最大的不同也是最难的地方）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public static ListNode insertionSortList(ListNode head) {
ListNode todo=head.next;
/*最坑的地方是在画图，总结到一个经验，画图其实不如调试，调试起来看变化，再画图微调最好，傻乎乎画图最后会绕死进去
* 添加一个表头节点非常有必要，这还是看题解发现的，不然插入时只能分情况讨论越来越复杂
* pre节点防止断裂，注意要及时更新pre节点
* todo这种变量名就不知所云，下次记得用cur
* */
ListNode dummyHead=new ListNode(0);
dummyHead.next=head;
ListNode todohead=dummyHead;
ListNode todopre=dummyHead.next;
while (todo!=null){
while(todohead.next!=null&& todo.val>todohead.next.val){
todohead=todohead.next;
}
if(todo==todohead.next){
/*不能用值的比较！！！！，这个是作为循环终止的条件（使用continue直接下一步，防止进行5步交换）：等到todohead.next循环到todo时，让todo后移，注意不仅仅要使得todo后移，todopre也要后移，todohead要归零*/
todo=todo.next;
todopre=todopre.next;
todohead=dummyHead;
continue;
}
todopre.next=todo.next;
todo.next=todohead.next;
todohead.next=todo;
todo=todopre.next;
todohead=dummyHead;
//这5步画图吧
}
return dummyHead.next;
}
|