@H_502_1@阅读目录
-
- 快速排序
@H_502_1@总结
前言：在前端大全中看到这句话，以此共勉。基础决定你可能达到的高度， 而业务决定了你的最低瓶颈
其实javascript算法在平时的编码中用处不大，不过不妨碍我们学习它，学习一下这些算法的思想，锻炼一下自己的思维模式。
本文不会每种方法都介绍一下，只介绍一下七种，纯属为了学习而学习，如果觉得代码不是很好理解，可以将数组里面的内容代入函数里面。
不过刚开始理解的时候确实挺头疼的。废话少说，搞起来！！
@H_502_1@冒泡排序
502_1@原理：
从第一个元素开始，往后比较，遇到比自己小的元素就交换位置
百度图片）
502_1@特点：
502_1@代码实现：
}
}
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(bubbleSort(arr)); // [1,5,100]
@H_502_1@插入排序
502_1@原理：
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据
如图所示
在插入排序中，数组会被划分为两种，“有序数组块”和“无序数组块”，
第一遍的时候从”无序数组块“中提取一个数20作为有序数组块。
第二遍的时候从”无序数组块“中提取一个数60有序的放到”有序数组块中“，也就是20，60。
第三遍的时候同理，不同的是发现10比有序数组的值都小，因此20，60位置后移，腾出一个位置让10插入。
然后按照这种规律就可以全部插入完毕。
下面是一张gif图
502_1@特点：
插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将第一个元素除外（让数组多一个空间才有插入的位置）.
第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中
比冒泡排序快一点
502_1@代码实现：
@H_502_1@希尔排序
502_1@原理：
希尔排序也叫 递减增量排序算法，是插入排序的一种神龟进化版。
什么叫递减增量呢，就是定义一个间隔序列，例如是5，3，1。第一次处理，会处理所有间隔为5的，
下一次会处理间隔为3的，最后一次处理间隔为1的元素。也就是相邻元素执行标准插入排序。
1、先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。 2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。 3、取第二个增量d2 4、直至所取的增量dt=1(dt 这里增量的取法如下： 第一次增量的取法为： d=count/2; 第二次增量的取法为: d=(count/2)/2; 最后一直到: d=1; 看上图观测的现象为： d=3时：将40跟50比，因50大，不交换。 将20跟30比，因30大，不交换。 将80跟60比，因60小，交换。 d=2时：将40跟60比，不交换，拿60跟30比交换，此时交换后的30又比前面的40小，又要将40和30交换，如上图。 将20跟50比，不交换，继续将50跟80比，不交换。 d=1时：这时就是前面讲的插入排序了，不过此时的序列已经差不多有序了，所以给插入排序带来了很大的性能提高。 502_1@特点： 由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中， 相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 打个比方，我原来的数组是[5,1]的，这样一打乱就全部重新排了。 502_1@代码实现： @H_502_1@归并排序 502_1@原理： 归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 502_1@有以下几个步骤： 1、把长度为n的输入序列分成两个长度为n/2的子序列; 2、对这两个子序列继续分为m/2的子序列，一直分下去 3、将两个排序好的子序列合并成一个最终的排序序列。 再来一张静态图，比较好理解
这里需要补充是，归并中对数组的分割是从上往下的，归并中数组的比较是从下往上的。
502_1@特点：
速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列.
属于分治思想，递归归并
502_1@代码实现：
502_1@原理：
1、在数据集之中，选择一个元素作为"基准"（pivot）。比如选择下面数字45
2、所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3、对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
502_1@特点：速度最快。和归并排序不同的是，归并排序是先分为两组再继续排，而快速排序是边分边排
502_1@代码实现：
//比基准小的放在left，比基准大的放在right
for(var i=0;i<arr.length;i++){
if(arr[i]<=pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
//递归
return quickSort(left).concat([pivot],quickSort(right));
}
var arr=[2,5];
console.log(quickSort(arr)); // [1,100]
@H_502_1@选择排序
502_1@原理：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后剩下的数当中找出最小的与第二个位置的数交换，如此循环直到倒数第二个数和最后一个数为止。
静态图：
502_1@特点：可以说是冒泡排序的衍生品，效率比较一般般
502_1@代码实现：
@H_502_1@奇偶排序
502_1@原理：
选取所有奇数列的元素与其右侧相邻的元素进行比较，将较小的元素排序在前面；
选取所有偶数列的元素与其右侧相邻的元素进行比较，将较小的元素排序在前面；
重复前面两步，直到所有序列有序为止。
如下图所示：
gif图：
502_1@特点：奇数和偶数序列交替比较
502_1@代码实现：
@H_502_1@总结
本文只是总结了算法中的一部分，算法的精髓就在于他们的思想，在js中用处应该不是很大。如果第一遍看不太懂那些代码，可以试着自己敲一遍，我在总结的时候，遇到理解不了的代码，自己敲完理解程度就会加深一些。
理解完，确实这些算法的实现思想博大精深，不得不感慨一下前辈们思想的深度。
原文链接：https://www.f2er.com/js/42652.html