新手必知数组排序实操步骤对数组进行排序的方法

文章插图
const arr = [49, 5, 14, 89, 71, 3, 10];// 一般写法arr.sort(function (a, b) {return a - b;// 按照升序排列 });// 箭头函数arr.sort((a, b) => a - b);// 结果[3, 5, 10, 14, 49, 71, 89]用归用，照葫芦画瓢不难，大家日常也是这么写的，没毛病！但是如果对一个方法不进行深入研究，那么就很容易踩坑，并且常常会填不了坑！
今天，我们重点聊聊比较函数 compareFunction 相关的知识。
为了接下来的思路能够更顺畅，在学习比较函数之前，我们先来了解一下有关插入排序的原理。
插入排序插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述：
一般来说，插入排序都采用 in-place 在数组上实现：
从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5 。动图演示：
插入排序
其实可以用一句话总结：从数组中第二个元素起（第一个元素已默认排序），每个元素都充当一次游标值，依次和它前面的（已排序）的元素相比较，如果游标值小，则将拿来比较的元素向后移一位，继续向前比较；否则，将游标值插入比较值的后面，结束比较。
关于比较函数 compareFunction如果想要 sort() 方法按照一定的规则进行排序（比如数字大小），那么就需要给它指定比较函数 compareFunction 。
如果指明了 compareFunction，那么数组会按照调用该函数的返回值排序，它有两个参数 a 和 b，返回值如下：
如果 compareFunction(a, b) 小于 0，那么 a 会被排列到 b 之前。如果 compareFunction(a, b) 等于 0，a 和 b 的相对位置不变。如果 compareFunction(a, b) 大于 0，b 会被排列到 a 之前。compareFunction(a, b) 必须总是对相同的输入返回相同的比较结果，否则排序的结果将是不确定的。compareFunction 初步探究我们暂不做什么复杂的分析，先使用控制台打印一下看看 a 和 b 到底是什么：
const arr = [49, 5, 14, 89, 71, 3, 10];console.log(arr);let times = 0;let res = [];arr.sort((a, b) => {res.push({times, a, b, "a - b": a - b});times++;return a - b;});console.log(res);console.log(arr);执行结果如下：
通过上图，我们可以看到：
a 的值在按照原数组中的顺序依次变化，这个排序采用的应该是插入排序法。a 代表的应该是游标。从 b 值的变化上又可以看出，a 首次找位置时采用了二分法，a < b 则向前比较，a>b 则向后比较。那么，其机理到底是不是我们所看到这样一个过程，还需要再探究。
compareFunction 深入探究要想弄清楚一个问题，还有什么比从根源上着手效率更高的呢？所以我们追根溯源，先来扒一扒 v8引擎的源码，看看它内部到底是怎么实现 sort 接口的。
下面的源码来自7.2版本之前的 v8，该版本之后的数组排序实现变化较大，暂不予讨论。
其中 array.js 文件下，关于 sort 接口实现的代码如下：
function InnerArraySort(array, length, comparefn) {// In-place QuickSort algorithm.// For short (length <= 22) arrays, insertion sort is used for efficiency.if (!IS_CALLABLE(comparefn)) {comparefn = function (x, y) {if (x === y) return 0;if (% _IsSmi(x) && % _IsSmi(y)) {return % SmiLexicographicCompare(x, y);}// 将数组元素转换为字符串x = TO_STRING(x);y = TO_STRING(y);if (x == y) return 0;else return x < y ? -1 : 1;};}var InsertionSort = function InsertionSort(a, from, to) {for (var i = from + 1; i < to; i++) {var element = a[i];for (var j = i - 1; j >= from; j--) {var tmp = a[j];// 调用比较函数 a: tmp, b: elementvar order = comparefn(tmp, element);if (order > 0) {a[j + 1] = tmp;} else {break;}}a[j + 1] = element;}};/*** some code here **/var QuickSort = function QuickSort(a, from, to) {/*** some code here **/};}function ArraySort(comparefn) {CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");var array = TO_OBJECT(this);var length = TO_LENGTH(array.length);return InnerArraySort(array, length, comparefn);}// 源码我就不放了，大家有兴趣研究的话，可以点击上面的链接自行查看代码分析：

以上关于本文的内容，仅作参考！温馨提示：如遇健康、疾病相关的问题，请您及时就医或请专业人士给予相关指导!

「四川龙网」www.sichuanlong.com小编还为您精选了以下内容，希望对您有所帮助：

新手必知数组排序实操步骤 对数组进行排序的方法

新手必知数组排序实操步骤对数组进行排序的方法