blog

排序

冒泡排序

通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

function bubbleSort(arr) {
  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]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

function insertion(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[i]) {
        arr.splice(j, 0, arr[i])
        arr.splice(i + 1, 1)
        break
      }
    }
  }
  return arr
}

快速排序

  1. 在数据集之中，选择一个元素作为"基准"（pivot）。
  2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
  3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
function quickSort(arr) {
  if (arr.length < 2) return arr

  const pivot = arr[0]
  const left = []
  const right = []

  for (let i = 1; i < arr.length; i++) {
    arr[i] >= pivot && right.push(arr[i])
    arr[i] < pivot && left.push(arr[i])
  }

  return quickSort(left).concat(pivot, quickSort(right))
}

上面的版本缺点是需要额外的存储器配置，以下为原地（in-place）分割方法

function quickSort(arr, left, right) {
  let len = arr.length
  let partitionIndex
  left = typeof left !== 'number' ? 0 : left
  right = typeof right !== 'number' ? len - 1 : right

  if (left < right) {
    partitionIndex = partition(arr, left, right)

    quickSort(arr, left, partitionIndex - 1)

    quickSort(arr, partitionIndex + 1, right)
  }

  return arr
}

function partition(arr, left, right) {
  let pivot = left
  let index = pivot + 1

  for (var i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index)
      index++
    }
  }

  swap(arr, pivot, index - 1)

  return index - 1;
}

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

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j
      }
    }

    let temp = arr[min]
    arr[min] = arr[i]
    arr[i] = temp
  }

  return arr
}

归并排序

递归法

  1. 把 n 个元素看成 n 个长度为 l 的有序子表
  2. 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
  3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止
function mergeSort(arr) {
  if (arr.length < 2) return arr

  function merge(left, right) {
    let final = []

    while (left.length && right.length) {
      final.push(left[0] <= right[0] ? left.shift() : right.shift())
    }
    return final.concat(left, right)
  }

  let mid = Math.floor(arr.length / 2)

  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

堆排序

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

  function max_heapify(start, end) {
    let dad = start
    let son = dad * 2 + 1

    if (son >= end) return

    if (son + 1 < end && arr[son] < arr[son + 1]){
      son++
    }

    if (arr[dad] <= arr[son]) {
      swap(dad, son)
      max_heapify(son, end)
    }
  }

  let len = arr.length

  for (let i = Math.floor(len / 2) - 1; i >= 0; i--){
    max_heapify(i, len)
  }

  for (let i = len - 1; i > 0; i--) {
    swap(0, i)
    max_heapify(0, i)
  }

  return arr
}

计数排序

  1. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
  2. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1
function countSort(arr) {
  let C = []

  for (let i = 0; i < arr.length; i++) {
    let num = arr[i]
    C[num] >= 1 ? C[num]++ : (C[num] = 1)
  }

  let sortArr = []

  for (let j = 0; j < C.length; j++) {
    if(C[j]){
      while(C[j]>0){
        sortArr.push(j)
        C[j] --
      }
    }
  }
  return sortArr
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要

// 不理解，先复制记录下来 ...
Array.prototype.bucketSort = function(num) {
  function swap(arr, i, j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
  const max = Math.max(...this)
  const min = Math.min(...this)
  const buckets = []
  const bucketsSize = Math.floor((max - min) / num) + 1
  for(let i = 0; i < this.length; i++) {
    const index = ~~(this[i] / bucketsSize)
    !buckets[index] && (buckets[index] = [])
    buckets[index].push(this[i])
    let l = buckets[index].length
    while(l > 0) {
      buckets[index][l] < buckets[index][l - 1] && swap(buckets[index], l, l - 1)
      l--
    }
  }
  let wrapBuckets = []
  for(let i = 0; i < buckets.length; i++) {
    buckets[i] && (wrapBuckets = wrapBuckets.concat(buckets[i]))
  }
  return wrapBuckets
}

← 排序→