1.常见排序算法：
常见的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序
9大算法
1.1.冒泡排序
- 双层for循环（一首一尾），找到交换值；
- O(n^2)
- 稳定排序（相邻元素相同，不会交换）
冒泡排序
改进：
数据完全有序的时候展现出最优时间复杂度，为O(n)
要使算法在最佳情况下有O(n)复杂度，需要做一些改进，增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了，直接退出。
1.2 选择排序、交换排序
冒泡的优化，
两个for循环，交换。
1.3 插入排序
算法描述
把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
重复上述过程直到最后一个元素被插入有序子数组中。
动图演示
插入排序
1.4
1.5
1.7 堆排序
“堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。”
解决办法:
求top N：从10000万个数里选出前100个最大的数据，初始化堆，那么用最大堆，还是最小堆呢？
应该选用最小堆的数据结构来解决，最顶端是最小值，再次遇到比它大的值，就可以入堆，入堆后重新调整堆，将小的值pass掉。这样我们就可以选出最大的前K个数据了。言外之意，假若我们要找出N个数据中最小的前k个数据，就要用最大堆了。
1.8计数排序
适用场景：
排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-750就OK啦；又比如一群人的年龄，用个0-150应该就可以了，再不济就用0-200喽。计数排序需要占用大量空间，它比较适用于数据比较集中的情况
1.9 桶排序
减少存储的数量，桶里面有多个数，桶里面排序（依赖其他排序算法）后，再连接起来。
- 适用场景：
数相差比较大，且不多的情况。
因为依赖其他排序算法，所有不稳定。
1.10 基数排序
先比较低位，在比较高位。
- 适用场景：
基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好。
变种例子：比较年月日的排序。
链表、二叉树、数组
动态规划、堆栈
链表（Linked List）
- 去重 deleteDumplicated
记住前一个位置pre，去重的时候会删除当前，把pre指向cur.next
func deleteDumplicatedNode(p *Node) *Node {
head := p
if p == nil || p.Next == nil {
return head
}
for p.Next != nil {
pre := p
step := p.Next
for step.Next != nil {
if p.Value == step.Value {
pre.Next = pre.Next.Next
step = step.Next
} else {
pre = step
step = step.Next
}
}
p = p.Next
}
return head
}
-
反转 reverse
pre
cur
next 三个变换 -
反转变异，reverse by k
- 采用上面方法，每次反转一个，一共反转k个。再走下一组。
- 借用栈的空间做。
-
区间反转，第n个，第m个之间。借助下角标n和m做计数。
-
判断链表有环
快慢指针，多次走之后，fast=2,slow=1，所以如果有环，已定相遇。
两种结果，fast=slow 是环, 并且此时fast超了slow一圈。
fast=null 是链表
求单链表的中间节点，也可以用快慢指针方法。
image.png
因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。
- 环的长度是多少？
fast-slow 走过的路，刚好一圈
因为差值是1。
或者，slow走过的路就是一圈。
或者，第一次相遇后，让fast停着不走了，slow继续走，记录到下次相遇时循环了几次。
- 如何找到环中第一个节点（即Linked List Cycle II）？
已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。
- 如何将有环的链表变成单链表（解除环）？
剪断Y
- 如何将有环的链表变成单链表（解除环）？
- 如何判断两个单链表是否有交点？如何找到第一个相交的节点？
如何判断两个单链表是否有交点？先判断两个链表是否有环，
如果一个有环一个没环，肯定不相交；
如果两个都没有环，判断两个列表的尾部是否相等；
如果两个都有环，判断一个链表上的Z点是否在另一个链表上。
如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。
二叉树（Binary Search）
动态规划（Dynamic）
网友评论