JavaScript中sort的底层实现 |
您所在的位置：网站首页 › js数组方法sort › JavaScript中sort的底层实现 |
JavaScript中sort的底层实现
|
前言
本文主要介绍js中常用的几种排序算法，并结合v8中相关源码分析sort实现的策略 常见排序算法首先温习下排序算法需要关注的两大要素 时间复杂度描述该算法的运行时间，通常用大O描述，附上一张时间复杂度曲线图帮助理解 度量一个算法在运行过程中占用存储空间大小 常见排序常见的十大经典排序算法就不在这科普了，根据特性可将它们从不同角度进行分类 是否基于比较：比较类排序和非比较类排序 是否稳定：稳定类排序和不稳定类排序 通常我们从是否基于排序的视角进行分类 比较类排序 通过比较来决定元素间的相对次序，其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。 非比较类排序 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 具体分类枚举可以结合下图理解 接下来我们写下几个常见的经典排序 快速排序快速排序主要使用递归分支的思想，通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。 var a = [ 25, 76, 34, 232, 6, 456, 221]; function quickSort(array) { var quick = function(arr) { if (arr.length > 1) const pivot = arr.splice(index, 1)[0] const left = [] const right = [] for (let i = 0; i < arr.length; i++) { if (arr[i] > pivot) { right.push(arr[i]) } else if (arr[i] = end) return if (son + 1 < end && arr[son] < arr[son + 1]) { son++ } if (arr[dad] = 0; i--) { max_heapify(i, len) } for (var j = len - 1; j > k; j--) { swap(0, j) max_heapify(0, j) } return arr } heap_sort(a); // [6, 25, 34, 76, 221, 232, 456] 复制代码 归并排序归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 var a = [25, 76, 34, 232, 6, 456, 221]; function mergeSort(array) { const merge = (right, left) => { const result = [] let il = 0 let ir = 0 while (il < left.length && ir < right.length) { if (left[il] < right[ir]) { result.push(left[il++]) } else { result.push(right[ir++]) } } while (il < left.length) { result.push(left[il++]) } while (ir < right.length) { result.push(right[ir++]) } return result } const mergeSort = array => { if (array.length === 1) { return array } const mid = Math.floor(array.length / 2) const left = array.slice(0, mid) const right = array.slice(mid, array.length) return merge(mergeSort(left), mergeSort(right)) } return mergeSort(array) } mergeSort(a); // [6, 25, 34, 76, 221, 232, 456] 复制代码最后附上一张各排序算法统计对照表: arr.sort([compareFunction]) 如果不传入 compareFunction，则元素按照转换为字符串的各个字符的 Unicode 位点进行排序，有些同学经常在整数排序上犯错误，多半是因为遗漏了这一规则 const names = ['tom', 'jesse', 'jack']; names.sort(); console.log(names); // ["jack", "jesse", "tom"] const array1 = [1, 30, 4, 21, 100000]; array1.sort(); console.log(array1); // [1, 100000, 21, 30, 4] 复制代码如果指明了 compareFunction 参数 ，那么数组会按照调用该函数的返回值排序，即 a 和 b 是两个将要被比较的元素： compareFunction（a, b）< 0，a 会被排列到 b 之前 compareFunction（a, b）=== 0，a 和 b 的相对位置不变 compareFunction（a, b）> 0，b 会被排列到 a 之前 sort源码分析查阅 v8源码sort部分 我们可以发现，对于需要排序的元素个数n，具体排序策略有几下中情形： 当 n10 时，采用三路快速排序； 10= from; j--) { var tmp = a[j]; var order = comparefn(tmp, element); if (order > 0) { a[j + 1] = tmp; } else { break; } } a[j + 1] = element; } } function GetThirdIndex(a, from, to) { // 元素个数大于1000时寻找哨兵元素 var t_array = new InternalArray(); var increment = 200 + ((to - from) & 15); var j = 0; from += 1; to -= 1; for (var i = from; i < to; i += increment) { t_array[j] = [i, a[i]]; j++; } t_array.sort(function(a, b) { return comparefn(a[1], b[1]); }); var third_index = t_array[t_array.length >> 1][0]; return third_index; } function QuickSort(a, from, to) { // 快速排序实现 //哨兵位置 var third_index = 0; while (true) { if (to - from 1000) { third_index = GetThirdIndex(a, from, to); } else { // 小于1000 直接取中点 third_index = from + ((to - from) >> 1); } // 下面开始快排 var v0 = a[from]; var v1 = a[to - 1]; var v2 = a[third_index]; var c01 = comparefn(v0, v1); if (c01 > 0) { var tmp = v0; v0 = v1; v1 = tmp; } var c02 = comparefn(v0, v2); if (c02 >= 0) { var tmp = v0; v0 = v2; v2 = v1; v1 = tmp; } else { var c12 = comparefn(v1, v2); if (c12 > 0) { var tmp = v1; v1 = v2; v2 = tmp; } } a[from] = v0; a[to - 1] = v2; var pivot = v1; var low_end = from + 1; var high_start = to - 1; a[third_index] = a[low_end]; a[low_end] = pivot; partition: for (var i = low_end + 1; i < high_start; i++) { var element = a[i]; var order = comparefn(element, pivot); if (order < 0) { a[i] = a[low_end]; a[low_end] = element; low_end++; } else if (order > 0) { do { high_start--; if (high_start == i) break partition; var top_elem = a[high_start]; order = comparefn(top_elem, pivot); } while (order > 0); a[i] = a[high_start]; a[high_start] = element; if (order < 0) { element = a[i]; a[i] = a[low_end]; a[low_end] = element; low_end++; } } } // 快排的核心思路，递归调用快速排序方法 if (to - high_start < low_end - from) { QuickSort(a, high_start, to); to = low_end; } else { QuickSort(a, from, low_end); from = high_start; } } } 复制代码 The End |
【本文地址】
今日新闻 |
推荐新闻 |