介绍

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 ${\displaystyle O(1)}$ 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

原理

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤 2~5

复杂度

• 平均时间复杂度$O(n^{2})$
• 最坏时间复杂度$O(n^{2})$
• 最优时间复杂度$O(n)$
• 空间复杂度：总共 $O(n)$ ，需要辅助空间 $O(1)$

动画

实现

JavaScript

/* In insertion sort, we divide the initial unsorted array into two parts;
 * sorted part and unsorted part. Initially the sorted part just has one
 * element (Array of only 1 element is a sorted array). We then pick up
 * element one by one from unsorted part; insert into the sorted part at
 * the correct position and expand sorted part one element at a time.
 */

function insertionSort (unsortedList) {
  const len = unsortedList.length
  for (let i = 1; i < len; i++) {
    let j
    const tmp = unsortedList[i] // Copy of the current element.
    /* Check through the sorted part and compare with the number in tmp. If large, shift the number */
    for (j = i - 1; j >= 0 && (unsortedList[j] > tmp); j--) {
      // Shift the number
      unsortedList[j + 1] = unsortedList[j]
    }
    // Insert the copied number at the correct position
    // in sorted part.
    unsortedList[j + 1] = tmp
  }
}

/**
 * @function insertionSortAlternativeImplementation
 * @description InsertionSort is a stable sorting algorithm
 * @param {Integer[]} array - Array of integers
 * @return {Integer[]} - Sorted array
 * @see [InsertionSort](https://en.wikipedia.org/wiki/Insertion_sort)
 */

/*
  * Big-O Analysis
      * Time Complexity
        - O(N^2) on average and worst case scenario
        - O(N) on best case scenario (when input array is already almost sorted)
      * Space Complexity
        - O(1)
*/

function insertionSortAlternativeImplementation (array) {
  const length = array.length
  if (length < 2) return array

  for (let i = 1; i < length; i++) {
    // Take current element in array
    const currentItem = array[i]
    // Take index of previous element in array
    let j = i - 1

    // While j >= 0 and previous element is greater than current element
    while (j >= 0 && array[j] > currentItem) {
      // Move previous, greater element towards the unsorted part
      array[j + 1] = array[j]
      j--
    }
    // Insert currentItem number at the correct position in sorted part.
    array[j + 1] = currentItem
  }
  // Return array sorted in ascending order
  return array
}

参考

• 插入排序 - 维基百科，自由的百科全书 (opens new window)