插入排序是一种排序算法，它在每次迭代中将未排序的元素放在合适的位置。插入排序的工作原理与我们在纸牌游戏中对手中的卡片进行排序类似。我们假设第一张卡片已经排序，然后我们选择一张未排序的卡片。如果未排序的卡片大于手中的卡片，则将其放在右侧，否则放在左侧。以同样的方式，其他未分类的卡片被取出并放在正确的位置。插入排序使用了类似的方法。

算法的动画

算法的图解

假设我们需要对以下数组进行排序。


初始数组

假定数组中的第一个元素已排序。取第二个元素并将其单独存储在key. 与第一个元素的key进行比较。如果第一个元素大于key，则将 key 放在第一个元素的前面。 | | | —- | | 如果第一个元素大于 key，则 key 放在第一个元素的前面。 |

现在，前两个元素已排序。

取第三个元素并将其与左侧的元素进行比较。将它放在比它小的元素后面。如果没有小于它的元素，则将其放在数组的开头。


将 1 放在开头

同样，将每个未排序的元素放在正确的位置。 | | | —- | | 将 4 放在 1 后面 |


将 3 放在 1 后面，数组已排序

算法的伪码

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

算法的实现

Insert Sort中有两个嵌套循环，外循环正好运行N次迭代。但内部循环运行变得越来越短
在最好的情况下，数组已经排序并且（a [j]> X）总是为假所以不需要移位数据，并且内部循环运行在O（1），
在最坏的情况下，数组被反向排序并且（a [j]> X）始终为真插入始终发生在数组的前端，并且内部循环以O（N）运行

// Insertion sort in Java

import java.util.Arrays;

class InsertionSort {

  void insertionSort(int array[]) {
    int size = array.length;

    for (int step = 1; step < size; step++) {
      int key = array[step];
      int j = step - 1;

      // Compare key with each element on the left of it until an element smaller than
      // it is found.
      // For descending order, change key<array[j] to key>array[j].
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }

      // Place key at after the element just smaller than it.
      array[j + 1] = key;
    }
  }

  // Driver code
  public static void main(String args[]) {
    int[] data = { 9, 5, 1, 4, 3 };
    InsertionSort is = new InsertionSort();
    is.insertionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

算法复杂度

时间复杂度
最好的	O(n)
最差	O(n2)
平均	O(n2)
空间复杂度	O(1)
稳定性	是的

时间复杂度

最坏时间复杂度：假设一个数组按升序排列，而你想按降序对其进行排序。在这种情况下，出现最坏情况的复杂性。

每个元素都必须与其他每个元素进行比较，因此，对于每第 n 个元素，进行 (n-1) 次比较。因此，总的比较次数 = n * (n-1) ，约等于 n2

最佳时间复杂度： O(n)
当数组已经排序时，外循环运行n次，而内循环根本不运行。所以只比较 n 次数。因此复杂性是线性的。
平均时间复杂度：当数组的元素处于混乱的顺序（既不升也不降）时，就会发生这种情况。O(n2)

空间复杂度

空间复杂度是O(1)因为使用了额外的变量key。

算法的应用

在以下情况下使用计数排序：

该数组具有少量元素
只剩下几个元素需要排序

相似的算法

冒泡排序
快速排序
归并排序
选择排序

数据结构与算法

插入排序（Insertion Sort）