相关代码已经托管到github上，欢迎指正bug.戳我
排序
冒泡
冒泡排序，就跟它的名字一样，你可以想象一条🐟现在在一个湖底。鱼肚子里面是我们将要排序的数据。这个鱼每隔一段时间会打个嗝（吐个泡泡），而这个泡泡中的数总是鱼肚子里面的最大值或者最小值。然后一个小朋友在岸上拿了一个泡泡收集器，把它吐出的泡泡一个一个按顺序放进机器里面。最后整个泡泡收集器中的数据都是有序的了。
1
2
3
4
5
6
7
8
9
for(let i = 0 ;i < 待排序数组(a)的长度;i++){
for(let j = 0;j<待排序数组(a)的长度-1-i;j++){
if(a[j]>a[j+1]){
let temp = a[j];
a[j] = a[j+1];
a[j+1] = a[j];
}
}
}
第一层for循环就是把鱼肚子里面的最大数吐出去。
第二层循环就是一个泡泡上升（不断交换）的过程。
时间复杂度：O(n*n)
（二分）插入排序
插入排序有一个前提：就是已经存在了一个已经排好顺序的数组了，这个时候我们在不断的将新的数插入到这个数组的过程。 二分策略（二分查找也是基于这种策略）：小时候玩的游戏–猜价格。一件商品让你猜价格。100？高了。这个时候再猜50？低了，再猜75…整个策略就是下一次取值总是取区间的中间位的数值。 查找的时间复杂度：O（nLog2^n）以2为底n的对数 平均时间复杂度：O(n*n)
希尔排序
希尔排序是一种分治思想的体现。
关于分治：
1
2
3
4
将原问题分成若干个较小的子问题，在递归的解决这些子问题，最后将自问题的解合并成原问题的解。主要分为三个步骤：
分解：将原问题分解成为一些列的子问题。
解决：递归的解决各个子问题，若子问题足够小，就直接解决。
合并：将子问题的解合并成原问题的解。
基本思想
先将整个集合，根据不同的步长分成若干个子集和，然后对各个子集和分别
进行直接插入排序，不断缩小步长直至1，最后一次步长为1的数组其实就是直接插入排序。但是因为之前步长每次减少的时候进行插入排序导致最后一次排序时数组元素基本有序。所以希尔排序的时间复杂的会比O(n*n)好一些。
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function doSort(a){
let len = a.length;
//stepSize 步长 其实就是不断的将一个数组划分为步长为stepSize的若干个子数组
for(let stepSize = len>>1;stepSize > 0 ;stepSize = stepSize >> 1){
//第一次步长为5 ，那么划分后的子数组为：0-5 1-6 2-7 3-8 4-9 5个子数组
//第二次步长为2，那么划分后的子数组为：0-2-4-6-8 和1-3-5-7-9 2个子数组
//第三次步长为1，那么划分后的子数组为：0-1-2-3-4-5-6-7-8-9 1个子数组
for(let i = stepSize;i<len;i++){
//对每个子数组进行排序
//这个地方要理解一个东西，比如说现在i是5,stepSize = 2,
//那么a[j](a[3])要是大于a[j](a[3+2]),两者交换，交换完之后j-= 2,所以a[3]是会和a[1]也会进行比较的。
//最好自己模拟一下加深一下印象
for(let j = i - stepSize;j >= 0&& a[j] >= a[j+stepSize];j-=stepSize){
let temp = a[j];
a[j] = a[j+stepSize];
a[j+stepSize] = temp;
}
}
}
console.info(a);
}
堆排序
基于堆这中数据结构弄的一个排序。
堆：有点像一个完全二叉树。一般分为小根堆大根堆。小根堆就是根节点放整个堆的最小值咯。同理大根堆你懂得。
堆的几个操作：
上浮
如果当前节点和它的父节点进行比较，如果这是一颗小根堆。如果存在当前节点比它的父节点小的情况，交换它们的位置。
下沉
如果小根堆中的父节点（如果有子节点）由于某种原因（经历过上浮操作被换到父节点这个位置或者是经历过…）大于它左右两个子节点，那么请交换它和左右两个子节点中最小的那个节点。
插入
每次把新添加的元素添加到最后一个节点位置，再让它进行上浮操作。
弹出
思想：将堆最上层（1号节点）的节点同最后一号位的节点进行交换，然后对1号节点进行下沉操作。
快速排序
思想：
- 先设置一个基准位（一般来以数组0号位置）。
- 从需排序数组的右边扫描一个小于基准点位元素值的值A，后暂时停止从右往左的扫描。
- 从需排序数组的左边开始扫描一个小于基准位元素值的值B，后暂时停止从左往右扫描。
- 在A的下标小于B的下标的前提下，交换A，B两个元素。
- 继续从右往左的扫描活动，并找到值C
- 继续从左往右的扫描活动，并找到值D
- …
- 当最后从右往左扫描与从左往右扫描暂时停下的位置时，停止所有的扫描活动，并且在这个时候交换基准位元素值和两侧扫描停止位置的元素值。确定第一个基准数。
- 基准数确定后，数组将被基准数一分为二个数组。分别对左右两个数组进行递归的调用同样的查找基准数策略即可。
时间复杂度：n * log n桶排序
思想：借助一个一维数组进行维护相关排序值和出现的频次。数组索引位对应排序值，数组索元素的值对应相关的出现频次。最后遍历整个数组输出元素不为0的索引位。
缺点：空间占用比较大，尤其是排序值中有一个数值很大的数。
优点：稳定、快。堆
