2018-03-11 几种常见算法

1. 冒泡排序Bubble Sort（体育委员摸头杀）

时间复杂度：O(n²)
有个数组a=[5,4,1,3,2,6]，从小到大排序，总共进行a.length-1轮，首先将a[0]和a[1]比较，谁大就把谁放在后面，交换完后再将a[1]和a[2]比较，谁大就把谁放在后面，交换完后再将a[2]和a[3]比较.....一直到a[4]和a[5]比较，进行完第一轮后，最大的那个就已经放在最后一位了，接下来再重新从a[0]开始......直到进行到a[3]和a[4]比较（a[5]上一轮已经确定了最大的，不用再动了），直到a[2],a[3],a[4],a[5]都确定了，最后再比较一次a[0],a[1]，排完a[0],a[1]的顺序，a数组的顺序就排好了~
点BUB是冒泡排序的动画演示

冒泡排序

2. 选择排序Selection Sort（体育老师点人法）

时间复杂度：O(n²)
选出最小的和第一位交换位置，第一位就被确定了，接下来找倒数第二小的和第二位换位置，接着再找倒数第三小的和第三位换位置......一直找到最后一位
点SEL是冒泡排序的动画演示

选择排序

3. 插入排序Insertion Sort（起扑克牌法）

时间复杂度：O(n²)
从数组的第二个开始，和第一个比较并排顺序，接着拿第三个和第二个比，若比第二个大则直接不动，若比第二个小则和第一个比，若比二小比一大则插在它们中间，若比第一个小则放在第一个，接着再拿第四个分别和三、二、一
比.......直到最后。
这就像打扑克牌时你摸牌的方法
点INS是冒泡排序的动画演示

4. 随机快排

优点：
效率高,时间复杂度：O(n*log2n)
缺点：
有时候比计数排序慢
简介：
随机选一个数，例：36，#将这个数和第一个数交换位置，于是36到了第一位，接着将36和其他所有数依次比较大小，把所有比36小的放左边，比36大的放右边，比完其他所有数后把36同比它小的数里的最右边的那个交换位置，这样36就定位了。
接着以同样的方式随机选择一个36左边的数，然后回到上面#的位置继续进行，在36的左边再次快排，这样左边排序时完全不用管右边，大大提高了效率，把左边排完再排右边。
演示：点R-Q是随机快排

5. 计数排序（Hash）

优点：
效率高，时间复杂度：O(n+max)
缺点：
1.需要一个hash来作为工具
2.无法对小数和负数进行排序，只能排正整数
3.可能需要很多桶，不像桶排序可控制桶数量
用途：
数字相差不大的时候可以用计数排序，如年龄排序
简介：
和基数排序差不多，比快排更快，需要一个额外数组(Hash)辅助，例：a=[3,2,4,5,1,3,34]
a[0]=3于是将Hash数组中的hash[3]=1
a[1]=2于是将hash[2]=1
a[2]=4于是将hash[4]=1
a[3]=5于是将hash[5]=1
a[4]=1于是将hash[1]=1
a[5]=3于是将hash[3]=hash[3]+1=2
a[6]=34于是将hash[34]=1
这样hash=[ ,1,1,2,1,1, , , , ,......, , , , ,1]
最后将hash中的数据按顺序取出来存放在另外一个数组里则排序完成。

6. 桶排序（Hash）

优点：
和计数排序不同的是一个桶里可放多个数字，效率高，计数排序的改良版，时间复杂度：O(N+C)
缺点：
需要hash工具，和计数排序不同的是每个桶里都是无序的，还要再排一次序
用途：
高考总分排序，每100分放在一个桶里，数字很分散的时候不好用，可用基数排序（比如从几十到几千）
简介：
a=[0,2,1,56,32,67,32]，存入hash里

hash = {
  '0':[0,2,1],
  '1':[],
  '2':[],
  '3':[32,32],
  '4':[],
  '5':[56],
  '6':[67],
}

还要把每个桶里的数字排序一下，再依次拿出来

7. 基数排序Radix Sort（Hash）

优点：
效率高
桶数量是确定的，时间复杂度：O(nlog(r)m)
缺点：
需要一个hash当工具，要多次排序
简介：
和桶排序类似，数字很分散的时候，可以用基数排序，首先用个位排，每次出桶的时候要按照进桶的顺序出！再到百位，再到千位，具体看下面演示

演示：点RAD是基数排序

8. 堆排序

时间复杂度：nlogn
用数组表示一个堆，每次都做最大堆排序，每做完一次就把最大的数和最后一位交换位置，并定下来，于是每做一次最大堆排序就能确定一个最大的数并把它放到最后一位，一直重复到排完所有的数，这样一个从小到大的数组就排出来了
演示：堆排序

9. 归并排序

本文版权归彭奕泽和饥人谷所有