常见排序算法详解（JavaScript实现）

2020-03-20 本文已影响0人 VaporSpace

时间复杂度：O(n^2)
原理：通过两层循环来实现，外层遍历整个数组，内层再遍历一次数组并找到未排序数组中的最小数组（通过迭代比较，不停去相对最小值），然后将最小值与第一个数组项对调，接着外循环进入第二轮，便从第二项数组开始重复上述操作，直到整个数组排列完毕；

image

时间复杂度：O(n^2)
原理：依然要通过两层循环，外循环便利每个数组项，内循环从外循环的数组项（i）开始往前遍历，如果当前数组项比前一个小，则与前一个调换位置，这样一直循环重复，数组就逐渐归位了；
其实本质上跟选择排序一样，通过两个循环来排序，插入排序虽然在内循环次数上一般会比选择排序边际递减地快，但也付出了大量的数组转换的操作；（代码下图①）
理论上来说插入和选择两种排序实际效率应该相近，但事实并非如此，在随机的数据表现上，插入排序是明显慢于选择排序，这主要是因为插入排序中大量的数组项值调换赋值的操作；
所以接下来要改进插入排序，减少数组项调换复制操作，替代为单向复制，在内循环中不再是比前一位小就调换，而是先将 j（当前项）的值取出，将 j-1 的值复制进目前的 j 项中，先不改变 j-1 的值，然后再拿当前项去跟 j-2 比，如果当前项还是更小，则重复之前操作，直到正确位置，再将当前项的值复制进去，这样就成功减少了近一半的赋值操作了；（代码下图②）
事实证明，优化过的插入排序，在十万随机数据级别已经领先排序一半了，更何况插入排序在找到正确位置后就会停止循环，对随机性较低的数据则有更大优势；（如下图）

image

插入和选择的性能比较^

image

①改进前 ^

image

②改进后 ^

时间复杂度：最坏还是O(n^2)
原理：希尔排序将插入排序作为它的子进程，它的核心是一个叫步长(gap)的概念，这个步长可以理解为一个类似疏密程度的概念。它共有3层循环，外层是以步长为循环，一般取数组的一半，循环一次再除一半，中层和里层就是插入排序的操作，不过不是跟前一项比，是跟当前索引减去步长后的那一项比。说到这里就可以理解为什么我说步长是类似疏密程度的概念，当步长不断除于2，变得越来越小，直到零停止循环，这个过程中，插入排序的比较项间越来越近，逐渐数组被排列出来。
其实也是利用插入排序在数据随机性较低情况下很高校这个特点，随着步长降低，整个排序循环越来越高效。

image

image

image

时间复杂度：最坏还是O(n*logn)；
原理：归并算法可以分为两部分，第一部分就是将一个数组两两分开，递归进行，直到分到只剩下1个，这时候进行第二部分，也就是核心部分，将每个单独项与邻近项再两两归并，并且在归并后进行一个排序，最后不停往回归并，直到归并成一个有序的数组；
那么这个归并后的排序怎么进行呢？我们知道，归并前有两个相邻数组，他们之间之前没有联系过，那怎么保证他们归并后是排好序的呢？首先将这两个要合并的数组成为arr1，然后再将这两个组数组复制一份成为arr2（再将arr1的两个数组合并），然后将arr2中两个数组从头开始依次以擂台的形式互比，谁小谁就先被赋值回arr1较前的位置，arr1从头往后按顺序赋值下去，直到排号序。最后通过这样递归的方式将整个数组排好序。我这里用了很多次“合并数组”这个词，但实际代码里为了性能更好，一般不会这样频繁操作数组，而是将数组的序号抽象出来，达到分开和归并的效果，具体代码看下图；

image

时间复杂度：在某些最坏的情况下复杂度为O(n^2)，如果是完全随机就是O(n*logn)；
原理：快速排序也是运用了分组递归的思想，首先找到这个分组的分界点（一般为当前数组首位），然后将这个分界点在数组中进行循环比较，最后让它回到它正确的位置，以此分界，分为两个数组递归下去，在这样的过程中逐渐完成排序。代码如下图。
这里有一个很重要的一步是，在分界点进行循环比较时，需要将比它小的数往前移，就是下图for循环里的数组对调。

image

在原理中，我提到，分界点一般取首位，但如果遇到近乎有序的数据时，就会出现O(n^2)的时间复杂度，要优化这一点，很简单，只要分界点去随机位就行，这样出现最坏情况的可能性虽然仍然会存在，但极低了，如下图；

image

还有一种情况就是如果数据中存在大量重复，也会导致递归分组下去会出现像上面那样分组极端不平衡的情况，最终时间复杂度会出现最坏的情况。为了解决这种情况，需要进行双向遍历，这次循环比较分界点分别从头尾两个方向同时进行，小等于分界点和大于等于分界点的被分别纳入两个分组，这样就能一定程度上将重复的数据分开。具体实现看下图，只改动了mid的取值，所以单独写了一个函数来取值；

image