常见排序算法回顾及总结

算法性能

插入排序

插入排序是比较符合人类直觉的排序方法，循环遍历数组，每一趟将一个待排序元素插入到有序队列的正确位置中，直到元素全部插入完成

算法流程

1. 将第一个元素视为有序队列
2. 取出下一个元素，在有序队列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置构成新的有序队列
6. 重复 2 ~ 5 直到排序完成

图解

代码实现

function InsertionSort (list) {
  for (let i = 1; i  0; j--) {
      if (curr < list[j - 1]) {
        list[j] = list[j - 1]
      } else {
        list[j] = curr
        break
      }
    }
  }
}

算法性能

特点

插入排序的特点是

• 队列越小，执行效率越高
• 队列的排序程度越好，执行效率越高

Google 的 V8 引擎实现的 Array.sort() 方法在数据量小于10时，使用的就是 插入排序

希尔排序

希尔排序于1959年由 Shell 发明，是第一个突破 O(n²) 的排序算法，基于插入排序改进而来，和插入排序的不同之处在于，它会使用间隔序列优先比较距离教员的元素，又叫 缩小增量排序

希尔排序的核心思想是：将记录按照间隔分组，对每组记录采用直接插入排序方法进行排序，然后逐渐缩小间隔排序，直到间隔缩小为1排序后即完成最终排序。

前面我们已经提到， 插入排序 在队列排序程度越好的情况下，执行效率越高，希尔排序就是利用这个特点优化的。

算法发明者 Donald Shell 最初建议采用 n/2, n/4, … , 1 这样的间隔序列，更深入的研究表明（由 Sedgewick 提出），最好的间隔序列为：1, 5, 19, 41, 109, …

算法流程

1. 选择一个间隔序列 t1，t2，…，tk，其中 ti > tj，tk=1
2. 按间隔序列个数 k 对序列进行 k 趟排序
3. 每趟排序，根据间隔 ti 将序列分为若干长度的的子序列，分别对子序列进行 插入排序
4. 当 tk = 1 时排序完成后，排序结束

图解

代码实现

function ShellSort (list) {
  const n = list.length
  for (let step = Math.floor(n / 2); step > 0; step = Math.floor(step / 2)) {
    for (let i = step; i = 0; j -= step) {
        if (temp < list[j]) {
          list[j + step] = list[j]
        } else {
          beak
        }
      }
      list[j + step] = temp
    }
  }
}

算法性能

选择排序

选择排序是一种非常简单直观的排序算法，循环遍历为排序序列，找出当中最小（或最大）的元素，放在已排序序列的顶端（或末端），直到元素全部排序完成。

算法流程

1. 初始状态下，无序区为 [1, n], 有序区为空
2. 第 i (i = 1, 2, …, n – 1)趟遍历开始时，有序区为 [1, i – 1]，无序区为 [i, n]，从无序区中遍历找到最小值（或最大）x，将它与无序区第一个元素交换，有序区更新为 [1, i]，无序区更新为 [i + 1, n]
3. 重复步骤 2，直到第 n – 1 趟结束

图解

代码实现

function SelectionSort (list) {
  for (let i = 0; i < list.lenght - 1; i++) {
    let min = i
    for (let j = i; j  list[j]) {
        min = j
      }
    }
    const temp = list[min]
    list[min] = list[i]
    list[i] = temp
  }
}

算法性能

归并排序

归并排序的核心思想是 分治法(Divide and Conquer) ，递归分割子序列进行归并操作，先使每个子序列有序，再使子序列段间有序。将两个有序表合并成一个有序表，称为二路归并。

算法流程

1. 将长度为 n 的序列对半分为左右两个子序列
2. 对两个子序列分别采用归并排序
3. 将排好序的子序列合并为最终的序列

图解

代码实现

function MergeSort (list) {
  if (list.length < 2) return list
  const middle = Math.floor(list.length / 2)
  const left = list.slice(0, middle)
  const right = list.slice(middle)
  return merge(MergeSort(left), MergeSort(right))
}

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

算法性能

快速排序

快速排序也是建立在分治法上，在序列中选择一个元素作为基准，将序列分为比基准小和比基准大的两个子序列，递归对子序列进行相同操作，直到整个序列有序

算法流程

1. 在序列中选择一个元素作为基准 (pivot)
2. 对序列进行重排列，比基准小的放在基准前，比基准大的放到基准后
3. 递归的对前后子序列重复步骤 1~2，直到排序完成

图解

代码实现

function QuickSort (list, left, right) {
  const len = list.length
  if (typeof left !== 'number') left = 0
  if (typeof right !== 'number') right = len - 1
  let pivot
  if (left < right) {
    pivot = partition(list, left, right)
    QuickSort(list, left, pivot - 1)
    QuickSort(list, pivot + 1, right)
  }
  return list
}
function partition (list, left, right) {
  let pivot = list[left]
  while (left < right) {
    while (left = pivot) {
      right--
    }
    list[left] = list[right]
    while (left < right && list[left] <= pivot) {
      left++
    }
    list[right] = list[left]
  }
  list[left] = pivot
  return left
}
function swap (list, i, j) {
  const temp = list[i]
  list[i] = list[j]
  list[j] = temp
}

算法性能

未完待续