js数组排序与Sort方法 javascript前端es6

时间复杂度&空间复杂度

文章图片

由图可知，时间复杂度应尽力控制在 O(nlogn) 以下。
空间复杂度，就是对一个算法在运行过程中临时占用存储空间大小的度量
js排序根据它们的特性，可以大致分为两种类型：比较类排序和非比较类排序。

比较类排序：通过比较来决定元素间的相对次序，其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

比较类排序

交换排序
- 冒泡排序
- 快速排序
插入排序
选择排序
- 普通选择排序
- 堆排序
归并排序

冒泡排序接触的第一个排序算法,逻辑比较简单

let testArr = [1, 3, 5, 3, 4, 54, 2423, 321, 4, 87]; function bubbleSort(arr) { const len = arr.length if (len < 2) return arr; for (let i = 0; i < len; i++) { for (let j = 0; j < i; j++) { if (arr[j] > arr[i]) { const tmp = arr[j]; arr[j] = arr[i] arr[i] = tmp } } } return arr }

快速排序快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。
最主要的思路是从数列中挑出一个元素，称为 “基准”（pivot）；然后重新排序数列，所有元素比基准值小的摆放在基准前面、比基准值大的摆在基准的后面；在这个区分搞定之后，该基准就处于数列的中间位置；然后把小于基准值元素的子数列（left）和大于基准值元素的子数列（right）递归地调用 quick 方法排序完成，这就是快排的思路。

function quickSort(array) { let quick = function (arr) { if (arr.length <= 1) return arr; // Math.floor() 返回小于或等于一个给定数字的最大整数 // 获取数组中间位数索引值 const index = Math.floor(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] <= pivot) { left.push(arr[i]) } } return quick(left).concat([pivot], quick(right)) } const result = quick(array) return result }

插入排序一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果。

function insertSort(array) { const len = array.length let current // 当前值 let prev // 前值索引 // 从1开始，拿到当前值current，和前值比较，如果前值大于当前值，就进行交换 for (let i = 1; i < len; i++) { // 记录下当前值 current = array[i] prev = i - 1; while (prev >= 0 && array[prev] > current) { array[prev + 1] = array[prev] prev-- } array[prev + 1] = current } return array }

选择排序选择排序是一种简单直观的排序算法。它的工作原理是，首先将最小的元素存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序的序列后面……以此类推，直到所有元素均排序完毕。最稳定的排序算法之一，因为无论什么数据进去都是 O(n 平方) 的时间复杂度，所以用到它的时候，数据规模越小越好

function selectSort(array) { const len = array.length let tmp; let minIdx; for (let i = 0; i < len - 1; i++) { minIdx = i; for (let j = i + 1; j < len; j++) { if (array[j] < array[minIdx]) { minIdx = j } } tmp = array[i] array[i] = array[minIdx] array[minIdx] = tmp } return array }

堆排序堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现。根节点最大的堆叫作大根堆，根节点最小的堆叫作小根堆。
核心点

堆排序最核心的点就在于排序前先建堆；
由于堆其实就是完全二叉树，如果父节点的序号为 n，那么叶子节点的序号就分别是 2n 和 2n+1

function heapSort(arr) { let len = arr.length // 构建堆 function buildMaxHeap(arr) { // 最后一个有子节点开始构建堆 for (let i = Math.floor(len / 2 - 1); i >= 0; i--) { // 对每一个非叶子节点进行堆调整 maxHeapify(arr, i) } }function swap(arr, i, j) { [arr[j], arr[i]] = [arr[i], arr[j]] }function maxHeapify(arr, i) { let left = 2 * i + 1; let right = 2 * i + 2 // i为该子树的根节点 let largest = i; if (left < len && arr[left] > arr[largest]) { largest = left } if (right < len && arr[right] > arr[largest]) { largest = right } // 当上面两个判断有一个生效时 if (largest !== i) { swap(arr, i, largest) // 交换之后，arr[i]下沉，继续进行调整 maxHeapify(arr, largest) } }buildMaxHeap(arr) for (let i = arr.length - 1; i > 0; i--) { swap(arr, 0, i) len--; maxHeapify(arr, 0) } return arr }

归并排序归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

function mergeSort(arr) { const merge = (right, left) => { const result = [] let idxLeft = 0 let idxRight = 0 while (idxLeft < left.length && idxRight < right.length) { if (left[idxLeft] < right[idxRight]) { result.push(left[idxLeft++]) } else { result.push(right[idxRight++]) } } while (idxLeft < left.length) { result.push(left[idxLeft++]) } while (idxRight < right[idxRight]) { result.push(right[idxRight++]) } return result } const mergeSort = arr => { if (arr.length === 1) return arr const mid = Math.floor(arr.length / 2) const left = arr.slice(0, mid) const right = arr.slice(mid, arr.length) return merge(mergeSort(left), mergeSort(right)) }return mergeSort(arr) }

归并排序是一种稳定的排序方法，和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好得多，因为始终都是 O(nlogn) 的时间复杂度。而代价是需要额外的内存空间。

时间复杂度，空间复杂度比较

文章图片

Array中Sort方法

arr.sort([compareFunction])

compareFunction 用来指定按某种顺序进行排列的函数，如果省略不写，元素按照转换为字符串的各个字符的 Unicode 位点进行排序

const months = ['March', 'Jan', 'Feb', 'Dec']; months.sort(); console.log(months) // [ 'Dec', 'Feb', 'Jan', 'March' ] const testArr = [1, 3, 5, 6, 3, 4, 54, 2423, 321, 4, 87]; testArr.sort(); console.log(testArr) // [1, 2423, 3, 3, 321, 4, 4, 5, 54, 6, 87]

如果指明了 compareFunction 参数，那么数组会按照调用该函数的返回值排序，即 a 和 b 是两个将要被比较的元素：

如果 compareFunction（a, b）小于 0，那么 a 会被排列到 b 之前；
如果 compareFunction（a, b）等于 0，a 和 b 的相对位置不变；
如果 compareFunction（a, b）大于 0，b 会被排列到 a 之前。

底层 sort 源码分析

当 n<=10 时，采用插入排序；
当 n>10 时，采用三路快速排序；
10
n>1000，每隔 200~215 个元素挑出一个元素，放到一个新数组中，然后对它排序，找到中间位置的数，以此作为中位数。

1. 为什么元素个数少的时候要采用插入排序？

虽然插入排序理论上是平均时间复杂度为 O(n^2) 的算法，快速排序是一个平均 O(nlogn) 级别的算法。但是别忘了，这只是理论上平均的时间复杂度估算，但是它们也有最好的时间复杂度情况，而插入排序在最好的情况下时间复杂度是 O(n)。
在实际情况中两者的算法复杂度前面都会有一个系数，当 n 足够小的时候，快速排序 nlogn 的优势会越来越小。倘若插入排序的 n 足够小，那么就会超过快排。而事实上正是如此，插入排序经过优化以后，对于小数据集的排序会有非常优越的性能，很多时候甚至会超过快排。因此，对于很小的数据量，应用插入排序是一个非常不错的选择。

2. 为什么要花这么大的力气选择哨兵元素？

因为快速排序的性能瓶颈在于递归的深度，最坏的情况是每次的哨兵都是最小元素或者最大元素，那么进行 partition（一边是小于哨兵的元素，另一边是大于哨兵的元素）时，就会有一边是空的。如果这么排下去，递归的层数就达到了 n , 而每一层的复杂度是 O(n)，因此快排这时候会退化成 O(n^2) 级别。
这种情况是要尽力避免的，那么如何来避免？就是让哨兵元素尽可能地处于数组的中间位置，让最大或者最小的情况尽可能少。

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); }function InnerArraySort(array, length, comparefn) { // 比较函数未传入 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; }; }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]; 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 <= 10) { InsertionSort(a, from, to); // 数据量小，使用插入排序，速度较快 return; }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; } } } }

【js数组排序与Sort方法】从上面的源码分析来看，当数据量小于 10 的时候用插入排序；当数据量大于 10 之后采用三路快排；当数据量为 10~1000 时候直接采用中位数为哨兵元素；当数据量大于 1000 的时候就开始寻找哨兵元素。
快速排序是不稳定排序，平均和最好时间复杂度都是O(nlogn),最差是O(n^2)，空间复杂度是O(nlogn)
插入排序是稳定排序，最好时时O(n),平均和最差是O(n^2),空间复杂度是O(1)