vlambda博客
学习文章列表

    今天先对插入排序进行整体介绍与图文解说，后续再对插入排序的优化（二分插入排序与希尔排序）分章节进行说明。

• 总体思想：对于 1 到 length(a)-1 之间每一个 index，将 a[index] 与 a[0] 到 a[index-1] 中比 a[index] 小的所有元素依次有序地进行交换。在索引index 逐步往右移动的过程中，它的左侧元素总是有序的，因此，当索引 index 到达数组的右端时整个数组就变成有序的了。总体来看， 

• index 左侧元素保持有序

• 新进的元素与之前有序的元素进行比较，使其再次达到有序

• 当元素的索引达到最右边的时候，整个数组达到有序

• 图文解说

• 和之前的数组一样，给定数组 a = [1, 3, 2, -1, 5, 7, 0]，采用插入排序对其进行升序排序

  
  




对照插入排序动态交换图，说明如下：

        - 目标：对数组 a = [1, 3, 2, -1, 5, 7, 0]进行升序排序

- 途径：插入排序

- 过程：
    - a[1] 元素，即元素 3， 此时 [1, 3] 数组有序，不用交换
    -  a[2 ] 元素，即元素 2 ，此时元素比 a[1] 小，因此 a[1]  和  a[2] 交换，此时元素变成 [1, 2, 3]。此时 2 > 1，数组  [1, 2, 3] 达到有序状态。
    - 再往后遍历，重复上一个步骤，使其左侧达到有序状态，以此类推。
    - 最后，生成有序数组 [-1, 0, 1, 2, 3, 5, 7]即为所求数组。

• 时间复杂度

• 外循环：遍历数组，时间复杂度 O(n)

• 内循环：当前 index 与之前的元素依次进行交换，直至达到有序状态。时间复杂度 O(n)

• 总的时间复杂度 O(n^2)

• 代码生成

• Python版本

def exchange(a, j, i): t = a[i] a[i] = a[j] a[j] = t
def insertSort(a): if not a or len(a) == 0: return a length = len(a) for index in range(1, length, 1): for j in range(index, -1, -1): if ( j > 0 and (a[j] < a[j-1])): exchange(a, j, j-1) return a




• Java版本

public class InsertSort{ public static void exchange(int[] a, int i, int j) { t = a[i]; a[i] = a[j]; a[j] = t; }  public static void sort(int[] a) {    // 将 数组 a 按插入排序的思路进行升序排列    int N = a.length;    for (int i=1; i < N; i++) {      // 将 a[i] 插入到 a[i-1], a[i-2],,,之中，并保持 a[0,,i]有序      for(int j=i; j > 0 && a[j] < a[j-1]; j--) {       exchange(a, j, j-1)      }    }  }}




• 优化 

• 插入排序时间复杂度为 O(n^2)，插入排序更适用的是部分数组有序，那么部分数组有序可以联想到二分查找，因此可以用二分查找来优化插入排序

• 插入排序每次交换的是相邻元素，那么是否可以交换不相邻元素来达到有序的目的呢，这个就是希尔排序。

• 该优化部分且听下回分解～即下一篇整体思路是对插入排序的优化解析，分两个章节来完成：

• 一个是二分插入排序，此时加入二分查找，同时会加入一些leetcode题目我们一起看看

• 另一个是希尔排序，希尔排序是对直接插入排序的一次升级优化，将相邻元素的交换优化成交换不相邻的元素以达到数组局部有序，最终达到整体有序的状态。