算法对大多数前端工程师来说都是一个比较不愿意提及的话题，因为学了，感觉在工作中直接应用的场景不多，不学，大厂面试必考算法，总结来说就是：没有学习算法的源动力，为面试学习算法总不会令人动力去学习，没有动力想要学好算法自然也很难，对我来说，学习算法的动力就是希望写出更高效率的代码，更好的理解各种前端框架的设计思路，因此，后面会写几篇有关算法与数据结构的学习笔记，下面进入这篇文章正题：排序算法
冒泡排序
排序算法中最简单最基础的就是冒泡排序，这种排序的思想就是相邻两个元素进行两两比较，大的放后面，每一轮选出最大的元素，让我们来看具体代码：
function bubbleSort(arr) { for (var i = 0; i < arr.length - 1; i++) { for (var j = 0; j < arr.length - i - 1; j++) { var temp; if (arr[j] > arr[j + 1]) { // 相邻两个元素比较，大的往后移动 temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } } console.log(arr)}bubbleSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])复制代码 为了更好的看到排序的过程，让我们来看下面动态图片：
冒泡排序，在数组本身就是有序的情况下(最好情况)，需要需要n-1次比较能完成，但是在最坏的情况下需要比较和交换n-1+n-2+n-3+...+1=n(n-1)/2次，其算法复杂度为O(n^2)
选择排序
选择排序是最直观简单的一种排序算法，具体实现思路就是：把第一个元素假定为最小元素，遍历后面没有排序的元素，如果发现比当最小元素小的值，就记下数组下标，循环执行，当一轮循环结束，将最小下标对应的值和当前元素调换位置，来看具体代码实现：
function selectionSort(arr) { var index,temp // index:最小值下标索引，temp:临时变量 for (var i = 0; i < arr.length; i++) { index = i for (var j = i + 1; j < arr.length; j++) { if (arr[j] < arr[index]) { index = j } } temp = arr[i] arr[i] = arr[index] arr[index] = temp } console.log(arr)}selectionSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])复制代码 为了更直观的展示排序的过程，让我们来看动态图片展示：
对于选择排序来说，比较次数是固定的，而交换次数则和数组的是否有序有关，但数组是正序时，不需要交换，当数组是倒序时，需要交换n-1次，它的时间复杂度是O(n^2)
插入排序
插入排序的实现思路和选择排序的实现思路有点类似，先将第一个元素设为已排序，然后遍历剩余的元素，如果已排序的元素大于当前的提取元素，已排序的元素向右移动一位，否则就将当前提取的元素插入，来看具体的代码实现：
function insetSort(arr) { for (var i = 0; i < arr.length; i++) { var temp = arr[i] // 提取出来的元素 var j = i - 1 while (arr[j] > temp) { // 比较已排序元素和当前提取出来的元素 arr[j+1] = arr[j] j-- } arr[j+1] = temp } console.log(arr)}insetSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])复制代码 插入排序在最好的情况下，也就是数组正序排列的时候，只要执行n-1次比较和0次交换时间复杂度为O(n)，当为倒序时，需要n^2/2次比较和n^2/2次交换，其时间复杂依然为O(n^2)
希尔排序
希尔排序又叫缩小增量排序，希尔排序的主要思想是使数组中任意相隔h的元素都是有序的，h就是希尔增量，实现的希尔排序的方法就是：对相隔h的元素进行分组，对每组进行使用插入排序，使子序列变成有序序列，增量逐渐递减一直到1为止，在例子中我将h增量设为array.length/2，递减的过程就是不断除以2，是不是被我的解释弄的有点晕，让我们先来看一个演示过程理解一下:
如图所示，一共15个元素，增量就是15/2为7，第一轮的分组即为[2, 26, 48],[44, 26],[38, 2],[5, 46],[47, 4],[15, 19],[36, 50],然后进行插入排序,得到新的序列[ 3, 27, 2, 5, 4, 15, 36, 26, 44, 38, 46, 47, 19, 50, 48 ]，然后在进行分组，增量为7/2为3：
第二轮分组[3, 5, 36, 2, 19],[44, 47, 26, 46, 50], [38, 15, 27, 4, 48],然后进行插入排序，得到序列[ 3, 4, 2, 5, 26, 15, 19, 27, 44, 36, 46, 47, 38, 50, 48 ]，然后再进行分组，增量为3/2为1，再插入排序得到的就是一个有序序列了，最好让我们来看具体的代码实现：
function shellSort(arr) { var n = arr.length for (var gap = parseInt(n/2); gap > 0; gap=parseInt(gap/2)) { for (var i=gap; i temp) { arr[j+gap] = arr[j] j = j - gap } arr[j+gap] = temp } } console.log(arr)}shellSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])复制代码 其实希尔排序也不难，只要按照上面的分解图示一步一步的理解去编写，相信大家都能写得出来，上面这种形式的增量设置就是二分的形式设置，然后插入排序，还有一种希尔排序的写法就是自定义增量，然后子序列里的元素两两比较，来看具体代码：
function shellSort(arr) { var n = arr.length, gap = 1 while (gap < n / 3) { gap = gap * 3 + 1 } for (gap; gap > 0; gap=parseInt(gap/3)) { for (var i=gap; i = 0; j-=gap) { if (arr[j] > arr[j+gap]) { var temp = arr[j+gap] arr[j+gap] = arr[j] arr[j] = temp } } } } console.log(arr)}shellSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])复制代码 希尔排序更高效的原因在于它权衡了子数组的规模和有序性，各个子数组都很短，排序之后的子数组都是部分有序的，因此在希尔排序的效率要比插入排序高。
分治法
在介绍归并排序和快速排序有必要先介绍一下分治法相关的内容，为什么呢？因为归并排序和快速排序都是分治法的典型应用。 分治法的设计思路就是：将一个大问题分解成若干个规模娇小的相同子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解 分治法所能解决的问题一般有如下几个特点：
- 把该问题缩小到一定规模就可以容易解决
- 该问题可以被分解为若干个规模较小的相同问题
- 利用该问题的子问题的解向上合并可以得到该问题的解
- 该问题分解出的子问题是相互独立的
归并排序
归并排序就是分治法的典型应用之一，归并排序的实现有两种，一种是自顶向下的归并排序，另一种就是自底向上的归并排序。
自顶向下的归并排序
向来看第一种，自顶向下的归并排序的实现思路是不断二分，然后对二分后的最小序列分别进行排序后，再将排序后的结果向上合并得到最终的有序数组，让我们先通过一个树结构来理解归并排序的过程：
从图中可以看到将一个数组0-14的元素不断二分，分到最后一层，然后互相比较，得到新的有序序列，然后向上合并，在进行比较，不断反复，合并出最终的有序序列，这就是自顶向下的归并排序的思路，通过这个思路你是否能自己写出排序的方法呢？
好了，接下来就让我们看看具体的代码实现:
function sort(arr) { var n = arr.length if (n < 2) return arr var mid = Math.ceil(n / 2) var left = arr.slice(0, mid) var right = arr.slice(mid) return merge(sort(left), sort(right));}function merge(left, right){ var result = [] while (left.length && right.length) { if (left[0] < right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) } return result;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(sort(arr))复制代码 代码实现是不是很容易理解呢？相信大家经过仔细的思考过后都能看得懂，为了方便更好的理解，来看一下动图的排序过程：
自底向上的归并排序
自底向上的归并排序思路是将长度为n的数组看成n个长度为1的数组，然后两两向上归并排序，得到新的数组，不断向上归并排序，直到得到长度为n的数组，这样的排序比之前自顶向下的排序代码要少，下面来看具体的代码实现：
function merge(arr, start, mid, end){ var i = start, j= mid + 1, copy = [] for (var k = start; k <= end; k++) { copy[k] = arr[k] } for (var k = start; k <= end; k++) { if (i > mid) { // 左边取完取右边的元素 arr[k] = copy[j] j++ } else if (j > end) { // 右边取完取左边的元素 arr[k] = copy[i] i++ } else if (copy[j] < copy[i]) { // 右边的元素小于左边的元素，取右边的元素 arr[k] = copy[j] j++ } else { // 左边的元素小于右边的元素，取左边的元素 arr[k] = copy[i] i++ } } console.log(arr)}function sort(arr) { var n = arr.length for (var i = 1; i < n; i = i + i) { // i子数组的大小 for (var j = 0; j < n - i; j = j + i + i) { // j数组的索引 var start = j var end = Math.min(j + i + i - 1, n-1) var mid = parseInt((start + end) / 2) merge(arr, start, mid, end) } }}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];sort(arr)复制代码 为了方便理解，已经在代码中加了必要的注释，可能这段代码比之前的要难理解一些，需要大家耐心多花一些时间去理解
快速排序
快速排序也是一种分治的排序算法，由于它实现简单并且效率比一般的排序算法高，因此，它的应用范围非常广泛，接下来让我们来看快速排序的排序过程：
将数组的第一个元素做为基准，从数组末尾开始找比基准小的数，找到就停下来，记下索引j，然后从基准右边开始找比基准大的数找到停下来，记下索引i，然后交换i和j上的元素，得到数组：
然后继续从44的位置开始找比基准3小的一直移动到2，此时索引i和索引j相等，将基准3和i、j对应的值交换位置得到：
此时基准数3前面的元素都是比它小的数，后面元素都是比它大的数，然后从基准数前后拆成两个数组，在递归执行前面同样的操作。 看来上面的排序过程，你是不是有代码的实现了呢？可以先试着写一下实现的代码，这样更容易理解，接下来就让我来看一下具体代码：
function sort(arr, left, right) { var temp = arr[left],i = left, j = right, t; if (left < right) { while (i != j) { while (arr[j] >= temp && i < j) { j-- } while (arr[i] <= temp && i < j) { i++ } if (i < j) { t = arr[i] arr[i] = arr[j] arr[j] = t } } arr[left] = arr[i] arr[i] = temp sort(arr, left, i - 1) sort(arr, i + 1, right) } return arr}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(sort(arr, 0, arr.length - 1))复制代码 看了代码之后是不是觉得并不难呢？这种快速排序的实现其实有一个问题不知道大家注意到没有，当数组中有多个重复元素的时候，重复的元素只要排了一个就不需要重复排了，但是这中快速排序的实现并没有考虑这种情况，即便重复的元素还是会执行排序，因此有人提出了更优的快速排序方法“三向切分的快速排序”，让我们先来看代码实现有什么不同：
function sort(arr, left, right) { var temp = arr[left],i = left, j = right,k = left + 1, t; if (left < right) { while (k <= j) { if (arr[k] < temp) { t = arr[k] arr[k] = arr[i] arr[i] = t i++; k++; } else if (arr[k] > temp) { t = arr[k] arr[k] = arr[j] arr[j] = t j--; } else { k++; } } sort(arr, left, i - 1) sort(arr, j + 1, right) } return arr}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,44,38];console.log(sort(arr, 0, arr.length - 1))复制代码 总体思路和之前的一样保证基准值前面的比它小后面的比它大，唯一不同的地方就是用了一个临时下标k去作比较，把小的丢到基准值前面，大的值就和末尾的值交换，得到新值再与基准值比较，当与基准值相等的时候，就只需要将临时下标的值+1而不需要排序了
总结
这篇文章主要介绍了几种常用的排序算法，也是个人算法学习的记录，后面会继续写一些关于算法与数据结构相关的内容，希望感兴趣的朋友可以多多关注。
如果本篇文章有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞收藏，希望能在评论里看到大家的交流