JS中的算法与数据结构之常见排序（Sort）算法详(2)

日期：2020-11-15 栏目：程序人生浏览：次

console.log( '原始数据:' + dataStore ); console.log( '选择排序:' + selectionSort( dataStore) ); // 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72 // 选择排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

3.插入排序（insertionSort）

插入排序有点类似人类按字母顺序对数据进行排序，就如同你打扑克牌一样，将摸来的扑克按大小放到合适的位置一样。它的原理就是通过嵌套循环，外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的元素进行比较；如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

实现步骤如下：

从第一个元素开始，该元素默认已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置

重复步骤2~5，直到排序完成

它的实现效果图如下：

插入排序

具体实现代码如下：

//插入排序 function insertionSort( data ) { var len = data.length; for (var i = 1; i < len; i++) { var key = data[i]; var j = i - 1; while ( j >= 0 && data[j] > key) { data[j + 1] = data[j]; j--; } data[j + 1] = key; } return data; }

排序结果如下：

console.log( '原始数据:' + dataStore ); console.log( '插入排序:' + insertionSort( dataStore) ); // 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72 // 插入排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

我们已经学习了三种基本的排序算法，其中冒泡排序是最慢的，插入排序是最快的，我们可以在运行的过程中通过 console.time('sortName') 和 console.timeEnd('sortName') 两个输出来看他们的效率如何，我这里给出一组值作为参考，实际中需要大量的数据测试和反复实验，进行数理统计后才能被视为有效的统计；

排序时间比较

高级排序算法

4.希尔排序（Shell Sort）

我们首先要学习的就是希尔排序，又称缩小增量排序，这个算法是在插入排序的基础上做了很大的改善，与插入排序不同的是，它首先会比较位置较远的元素，而非相邻的元素。这种方案可以使离正确位置很远的元素能够快速回到合适的位置，当算法进行遍历时，所有元素的间距会不断的减小，直到数据的末尾，此时比较的就是相邻元素了。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。

好吧，我还是用个案例来解释，这样会更清晰，我们以下面一组数据为例：

JS中的算法与数据结构之常见排序（Sort）算法详