关于 Array.sort

[liangbus]

数组的 sort 方法顾名思义，就是排序的意思，我们常用它来对一个数组进行升/降序排序

arr.sort([compareFunction])

它接受一个函数作为参数，其函数传入的参数为 cur, next. 当前与下一个需要比较的元素

如果 sort 参数为空，则元素按照转换为的字符串的各个字符的Unicode位点进行排序。即 Jack 会排在 Tom 之前，100 会排在 2 之前。

传入函数的 return 值如果小于 0，位置不变
如果大于0，则交换两个元素的位置

See? 是不是有点像冒泡，不急，这个我们后面再来对比

用是大家都会用的了，下面来对比一下其他排序方法的性能，来确保它值不值得使用

对比之前，我们先来创建一个随机的数组，这时候，sort 方法又派上了用场：用 sort 方法打乱一个数组，其实很简单，就一行代码

// 因为 random 方法会返回 0-1 (not included) 的随机数，为确保比较平均，因此取中间值 0.5 
arr.sort(() => {return 0.5 - Math.random()})

一个生成随机数组的方法（纯个人瞎想的，不完美，因为是连续的）

function generateRandomArray(len) {
	let i = 0;
	const arr = []
	while(i++ < len) {
		arr.push(i)
	}
	return arr.sort(() => 0.5 - Math.random())
}

手写个冒泡

const bubleSort = function(arr) {
  if (!arr.length) return []
  for(let i = 0; i < arr.length - 1; i++) {
    for(let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr
}

再手写个快排

const quickSort = function(arr){
  if (!arr.length) return [];
  const pivotKey = Math.floor(arr.length/2);
  const pivot = arr.splice(pivotKey, 1)[0]
  const leftArr = [], rightArr = []
  for (let i = 0; i < arr.length; i++) {
    let tmp = arr[i];
    if (tmp < pivot) {
      leftArr.push(tmp)
    } else {
      rightArr.push(tmp)
    }
  }
  return quickSort(leftArr).concat([pivot], quickSort(rightArr));
}

开始对比

// 千万级别排序
// 原生 sort 方法
const longArray = generateRandomArray(10000000)
const start = new Date().getTime()
longArray.sort((cur, next) => { return cur > next ? 1 : -1})
const end = new Date().getTime()
console.log(`Sort Func  cost ${end - start} milli sec`);
VM97:5 Sort Func  cost 4618 milli sec

ort Func  cost 2221 milli sec  // 500w
Sort Func  cost 409 milli sec  // 100w 


// 快排
const longArray3 = generateRandomArray(10000000)
const quickStart = new Date().getTime()
quickSort(longArray3)
const quickEnd = new Date().getTime()
console.log(`Quick Func cost ${quickEnd - quickStart} milli sec`);
VM122:5 Quick Func cost 8188 milli sec

Quick Func cost 3723 milli sec  // 500w
Quick Func cost 712 milli sec  // 100w

// 冒泡排序 10w 量级还能排，上了百万级别，浏览器直接没响应了，是我电脑太菜了吗？所以冒泡直接测试不了
那么，sort 的内部实现应该也不是冒泡吧（坐等 pia pia 打脸）

从上可以看出 sort 的性能快还排还要好，量越大，越明显
从网上查阅的资料得知道不同浏览器引擎的 sort 方法实现方式是不太一样，Chrome 的 V8 是用快排和插入排序实现的（没有阅读源码，仅参考网上文章资料）

Anyway, 假如不考虑浏览器差异性以及稳定性因素，使用 sort 方法都是比较好的选择

最后附上一些常见排序实现的代码
冒泡排序
选择排序
插入排序
归并排序
快速排序

参考：
MDN-Array.prototype.sort()
深入浅出 JavaScript 的Array.prototype.sort 排序算法
几大排序算法图示