直接插入排序

直接插入排序

基本原理

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数新增1的有序表。类似理扑克牌。

时间复杂度O(\(n^2\))

代码

public static void insertSort(int[] input) {
  int length = input.length;

  for (int i = 1; i < length; i++) {
    int key = input[i];
    int j = i-1;

    while (j >= 0 && input[j] > key) {
      input[j + 1] = input[j];
      j = j-1;
    }

    input[j + 1] = key;
  }

}

插入排序的特点

• 稳定排序
• in-place ，主需要一个记录的辅助空间
• 整体性能优于另外两类简单排序（冒泡和选择排序）

最好的情况

要排序的序列本身就是有序的， 每次对比只会和前一个，并且没有移动操作， 时间复杂度为O(n)

最差的情况

要排序的序列是逆序的，每次迭代都要和前面所有元素对比，并且每轮都会有移动，时间复杂度O(\(n^2\))