插入排序

INSERTION-SORT

形式化描述

输入：n个数的一个序列<a₁, a₂, ..., a_n>

输出：输入序列的一个排列<a₁^', a₂^', ..., a_n^'>，满足a₁^' <= a₂^' <= ... <= a_n^'

伪代码

for i = 2 to A.length
  key = A[i]
  // 将 key（A[i]）插入到已经排好序的 A[1..i-1]
  j = i - 1
  while j > 0 && A[j] > key
    A[j + 1] = A[j]
    j --
  A[j + 1] = key

代码

javascript

function sort(A) {
  if (A.length >= 2) {
    for (let i = 1; i < A.length; i++) {
      const key = A[i]
      let j = i - 1
      while (j >= 0 && A[j] > key) {
        A[j + 1] = A[j]
        j--
      }
      A[j + 1] = key
    }
  }
  return A
}

示例