你真的了解JavaScript Array#sort 吗?- 如何写一个比内建排序函数运行更快的排序函数

2019-06-17

本文主要讲解 javascript Array#sort 的两个方面:排序原理和排序算法。

排序原理

根据MDN文档,javascript Array#sort 默认是按照字符的UTF-16编码字典序排序,数组中的数字在排序的时候会被转换成字符,所以就会产生如下结果:

const myArray = [33, 2, 98, 25, 4]
myArray.sort() // [ 2, 25, 33, 4, 98 ]

const strings = ['80', '9']
strings.sort() // ['80', '9']

我们可以查看一下8和9的Unicode代码:

"8".codePointAt(0)  // 56
"9".codePointAt(0)  // 57

这样我们就知道了为什么80会排在9前面,为了让数字按照从小到大的顺序排列,我们可以给 sort() 传递一个排序函数:

const myArray = [33, 2, 98, 25, 4]
myArray.sort((a, b) => a - b) // [ 2, 4, 25, 33, 98 ]

排序算法

javascript内建的排序算法是很好用,但是我们也可以构建自己的排序算法,通常来说编程语言内建的排序算法已经很快了,但是如果你的程序对运行效率很敏感的话,可以构建出比内建函数函数更快的算法,这里我们就介绍三种算法,以及他们的运行效率速度对比: - insertion sort

function InsertionSort(arr) {
  let len = arr.length,         
        value,                      
        i,                         
        j;                 

    for(i = 1; i < len; i++) {
        value = arr[i]
        j = i - 1

        while (j >= 0 && arr[j] > value) {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = value
    }

    return arr
}
  • merge sort
function MergeSort(arr) {

  let len = arr.length,       
      middle,                     
      left,                      
      right,                    

  if (len < 2) {
    return arr
  }

  middle = Math.floor(len/2)


  left = arr.slice(0, middle)   
  right = arr.slice(middle)    

  return merge(MergeSort(left), MergeSort(right))

}

function merge(left, right) {
  let result = [],
      i = 0,
      j = 0

  while(i < left.length && j < right.length) {

    if(left[i] < right[j]) {
      result.push(left[i++])      
    } else {                  
      result.push(right[j++])
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j))
}
  • quick sort
function QuickSort(arr, left = 0, right = arr.length - 1) {
  let len = arr.length,
      index

  if(len > 1) {

    index = partition(arr, left, right)

    if(left < index - 1) {
      QuickSort(arr, left, index - 1)
    } 

    if(index < right) {
      QuickSort(arr, index, right)
    }

  }

  return arr

}

function partition(arr, left, right) {
  let middle = Math.floor((right + left) / 2),
      pivot = arr[middle],
      i = left,                
      j = right                

  while(i <= j) {

    while(arr[i] < pivot) {
      i++
    }

    while(arr[j] > pivot) {
      j--
    }

    if(i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      i++
      j--
    }
  }

  return i
}

算法运行效率对比图: 查看V8引擎的 javascript 源码你能看到,javascript排序函数使用js代码实现的,这样做的原因是js排序函数允许传入一个回调函数,如果使用cpp来实现js排序函数,需要在js函数和cpp函数之间来回切换,这样会非常影响运行效率,所以直接在同一个语言上下文实现排序函数。

参考