[算法详解][插入排序]Insertion Sort

• 基本思想
• 步骤
• 实例分析
• 伪代码
• 代码实现JAVA
• 性能分析
• 应用：常见面试题目

【基本思想】

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

【步骤】

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

【实例分析】

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4]，共有八个记录，排序过程如下：
[5] 6 3 1 8 7 2 4
[5, 6] 3 1 8 7 2 4
[3, 5, 6] 1 8 7 2 4
[1, 3, 5, 6] 8 7 2 4
[1, 3, 5, 6, 8] 7 2 4
[1, 3, 5, 6, 7, 8] 2 4
[1, 2, 3, 5, 6, 7, 8] 4
[1, 2, 3, 4, 5, 6, 7, 8]

【伪代码】

INSERTION-SORT（A）
   for j=2 to A.length
       key = A[j]
       //Insert A[j] into the sorted sequence A[1..j-1]
       i = j - 1
       while i > 0 and A[i] > key
           A[i+1] = A[i]
           i = i - 1
       A[i+1]=key

【JAVA代码实现】

   public static void main(String[] args)
   {
      int[] arr = {5, 6, 3, 1, 8, 7, 2, 4};
      sort(arr);
   }
   public static void sort(int[] arr) {
      if(arr.length<=1) {return;}
      for(int j = 1; j < arr.length; j++) {
         int key = arr[j];
         int i = j-1;
         while(i >= 0 && arr[i] > key) {
            arr[i+1] = arr[i];
            i--;
         }
         arr[i+1] = key;
      }
   }

【性能分析】

1. 最优
时间复杂度为O(n)
在最好情况下，若输入已排序，插入排序的时间复杂度在O(n)，即线性时间上完成排序。
2. 最坏
时间复杂度为O(n^2)
若输入数组反方向排序，即按照递减排序排好了序,则导致最坏情况。我们必须把每个元素A[j]与整个已排序子数组A[1..j-1]中的每个元素都要进行比较
3. 平均
O(n^2)
平均情况和最坏情况差不多，复杂度也在O(n2)
4. 空间复杂度
O(1)
5. 稳定性
相等元素的前后顺序没有改变，稳定排序

【应用：常见面试题目】

Leetcode 147. Insertion Sort List

参考：常见排序算法 - 插入排序