JavaScript 排序算法

[PolluxLee]

算法复杂度

排序方式	平均	最坏	最好	空间	稳定性
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
希尔排序	O(n^1.3)			O(1)	不稳定
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
快速排序	O(nlog2n)	O(n^2)	O(nlog2n)	O(log2n)	不稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定

Preparation（交换）

  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
  }

Bubble Sort（冒泡排序）

插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)

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

Selection Sort（选择排序）

  function selectionSort(arr) {
    let len = arr.length
    let minIdx
    for (let i = 0; i < len - 1; i++) {
      minIdx = i
      for (let j = i + 1; j < len; j++) {
        if (arr[j] < arr[minIdx]) {
          minIdx = j
        }
      }
      if (i !== minIdx) swap(arr, i, minIdx)
    }
    return arr;
  }

Insertion Sort（插入排序）

插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)

  function insertionSort(arr) {
    let len = arr.length
    for (let i = 1; i < len; i++) {
      let preIdx = i - 1
      let cur = arr[i]
      while (preIdx >= 0 && arr[preIdx] > cur) {
        arr[preIdx + 1] = arr[preIdx]
        preIdx--
      }
      arr[preIdx + 1] = cur
    }
    return arr
  }

Radix Sort（基数排序）

/*
[99,15,48,75,46,37,90,100]

// 第一步

0 90 100
1 
2
3
4
5 15 75
6 46
7 37
8 48
9 99

=> 90 100 15 75 46 37 48 99

// 第二步

0 100
1 15
2
3 37
4 46 48
5
6
7 75
8
9 90 99

=> 100 15 37 46 48 75 90 99

// 第三步

0 15 37 46 48 75 90 99
1 100 
2
3
4
5
6
7
8
9

=> 15 37 46 48 75 90 99 100

*/

  function radixSort(arr, maxDigit) {
    let counter = []
    let mod = 10
    let div = 1
    for (let i = 0; i < maxDigit; i++, div*=10, mod*=10) {
      for (let el of arr) {
        let pos = parseInt(el / div % mod)
        if (!counter[pos]) {
          counter[pos] = []
        }
        counter[pos].push(el)
      }
      arr = []
      for (let bucket of counter) {
        if (!bucket) continue
        let value
        while ((value = bucket.shift()) !== undefined) {
          arr.push(value)
        }
      }
    }
    return arr
  }

Quicksort（快速排序）

快速排序使用 分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）

步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot）
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为 分区（partition） 操作
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去

function partition(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= pivot) high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function partition2(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

function quickSort(arr, low, high) {
  if (low < high) {
    let pivotLoc = partition2(arr, low, high);
    quickSort(arr, low, pivotLoc - 1);
    quickSort(arr, pivotLoc + 1, high);
  }
}

let arr = [23,1,6,14,54,33,76,98,21,10];
quickSort(arr, 0, 9);

console.log(arr);

Merge Sort（归并排序）

  function merge(left, right){
    let result = []
    while (left.length > 0 && right.length > 0) {
      if (left[0] <= right[0]) {
        result.push(left.shift())
      }
      else {
        result.push(right.shift())
      }
    }
    while (left.length > 0) {
      result.push(left.shift())
    }
    while (right.length > 0) {
      result.push(right.shift())
    }
    return result
  }

  function mergeSort(arr) {
    let len = arr.length
    if (len < 2) return arr
    let mid = Math.floor(len / 2)
    let left = arr.slice(0, mid)
    let right = arr.slice(mid)
    return merge(mergeSort(left), mergeSort(right))
  }