| 算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n*n) | O(n) | O(n*n) | O(1) | 稳定 |
| 选择排序 | O(n*n) | O(n*n) | O(n*n) | O(1) | 不稳定 |
| 插入排序 | O(n*n) | O(n) | O(n*n) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O(nlog^2n) | O(nlog^2n) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n*n) | O(logn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序实现链表排序
-
分割：通过快慢指针
需要注意，因为是链表的缘故，需要像数组一样，考虑开区间、闭区间的问题，一种方法是：将连边分割为两条，通过tmp分割
-
合并：需要开辟额外空间，合并链表
func sortList(head *ListNode) *ListNode {
//1.分割
//分割到最后一个单位或nil时停止
if head==nil || head.Next==nil{
return head
}
//快慢指针实现二分的效果
slow, fast := head, head.Next
for fast!=nil && fast.Next!=nil{
slow = slow.Next
fast = fast.Next.Next
}
//注意：把两段链表分开，否则可能会有一些边界条件，类似开区间的概念
tmp := slow.Next
slow.Next = nil
left := sortList(head)
right := sortList(tmp)
//2.合并
//相当于开辟的额外空间，用一个虚头节点，便于返回合并后的链表
dummy := &ListNode{}
cur := dummy
for left!=nil || right!=nil {
//合并的过程
if left==nil{
cur.Next = right
right = right.Next
cur = cur.Next
continue
}
if right==nil{
cur.Next = left
left = left.Next
cur = cur.Next
continue
}
if left.Val<=right.Val{
cur.Next = left
left = left.Next
}else{
cur.Next = right
right = right.Next
}
cur = cur.Next
}
return dummy.Next
}
冒泡思路：
1.可以直接交换value
2.如果考虑交换节点的话：
需要考虑一个标志位~
可以通过一个sum来实现
每次遍历的时候count++，知直到等于sum，实现类似数组的思想
不知道对不对，欢迎留言