转载

插入排序

前言

本篇来学习十大排序中的插入排序，学习其算法思想并尝试实现排序。

插入排序有两种：

直接插入排序
折半插入排序

直接插入排序

直接插入排序（4，3，1，2）的流程如下图：

插入排序

对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其过程大概是这样的：

第一个元素就认为是有序的
取第二个元素，判断是否大于第一个元素。若是大于，表示已经有序，不用移动，否则将已经有序的序列整体向后移动一个位置
依此类推，直到所有元素已经有序。

可以借助上面的图来理解。

时间复杂度

需要到两层循环来处理，外层循环用于跑多少趟，而内层循环用于移动元素位置，因此时间复杂度仍为 O ( n ² )

伪代码

  void insertSort(int a[], int len) {   for i = 1; i < len; ++i {         // 后者>前者，才需要移动和插入     if a[i] < a[i - 1] {         // 记录下要移动的元素         int target = a[i];                  // 将前j-1个有序的元素分别后移一个位置         int j = i;         while j > 0 && a[j - 1] > target {           a[j] = a[j - 1];           j--;         }                  // 将目标元素插入对应的位置，使之有序         a[j] = target;     }   } }

C语言版

  void insertSort(int a[], int len) {   for (int i = 1; i < len; ++i) {          // 遇到不是有序的，才进入移动元素     if (a[i] < a[i - 1]) {       int target = a[i];         // 移动前j-1元素，分别向后移动一个位置       int j = i;       while (j > 0 && a[j - 1] > target) {         a[j] = a[j - 1];                  j--;       }              // 将目标元素放到目标位置，使之有序       a[j] = target;     }   } }

OjbC版

  - (void)insertSort:(int[])alen:(int)len {   for (int i = 1; i < len; ++i) {          // 遇到不是有序的，才进入移动元素     if (a[i] < a[i - 1]) {       int target = a[i];              // 移动前j-1元素，分别向后移动一个位置       int j = i;       while (j > 0 && a[j - 1] > target) {         a[j] = a[j - 1];                  j--;       }              // 将目标元素放到目标位置，使之有序       a[j] = target;     }   } }

Swift版

  funcinsertSort(vara: [Int]) ->[Int] {   forvar i = 1; i < a.count; ++i {     if a[i] < a[i - 1] {       lettarget = a[i]              var j = i       while j > 0 && a[j - 1] > target {         a[j] = a[j - 1]                  j--       }              a[j] = target     }   }      return a }

折半插入排序

从第二个元素开始逐个置入监视哨，使用low、high标签进行折半判断比较大小，并确认插入位置，该位置到最后一个数全部后移一位，然后腾出该位置，把监视哨里面的数置入该位置。依此类推进行排序，直到最后一个数比较完毕。

时间复杂度

折半插入排序, 即查找插入点的位置, 可以使用折半查找，这样可以减少比较的次数, 但是移动的次数不变，因此，时间复杂度仍为 O(n ²⁾ ;

伪代码

  void binaryInsertSort(int a[], int len) {   forint i = 2; i < len; ++i {     // 将元素放到哨兵的位置     a[0] = a[i];          int low = 1;     int high = i - 1;          // 折半查找位置     while low <= high {         int mid = (low + high) / 2;                  // 在低半区         if a[mid] > a[0] {           high = mid - 1;         } else { // 在高半区           low = mid + 1;         }     }          // 将前i - 1个元素后移     // 找到high，那么high+1就是i要插入的位置       forint j = i - 1; j >= high + 1; --j {         a[j + 1] = a[j];     }          // 将临时放在岗哨的元素放到所查找到的位置处     a[high + 1] = a[0];   } }

C语言版

  void binaryInsertSort(int a[], int len) {   for (int i = 2; i < len; ++i) {     // 第一个位置永远只是当作哨兵用     a[0] = a[i];          int low = 1;     int high = i - 1;          while (low <= high) {       int mid = (low + high) / 2;              if (a[mid] > a[0]) {         high = mid - 1;       } else {         low = mid + 1;       }     }          // 移动前i - 1个元素     for (int j = i - 1; j >= high + 1; --j) {       a[j + 1] = a[j];     }          // 放到查找到的位置处     a[high + 1] = a[0];   } }

Swift版

  funcbinaryInsertSort(vara: [Int]) ->[Int] {   forvar i = 2; i < a.count; ++i {     a[0] = a[i]          var low = 1     varhigh = i - 1     while low <= high {       letmid = (low + high) / 2              if a[mid] > a[0] {         high = mid - 1       } else {         low = mid + 1       }     }          forvar j = i - 1; j >= high + 1; --j {       a[j + 1] = a[j]     }          a[high + 1] = a[0]   }      return a }

感悟

对于折半插入排序算法，它需要一个哨兵，数组的0号位置是用作哨兵，而不存储数据。为什么所找到的位置是high+1呢？因为最后退出while循环一定是high = mid – 1之后，导致条件low > high而退出。所以，最后所找到的位置一定是high = mid – 1，由于减了1，所以应该插入的位置是high + 1。

当年大学的时候都没有这么认真地理解过，现在再回头理一遍，感觉当年大学时期学得真的好浅，压根没有真正地理解。现在在理解之后，能随手写出来了。

关注我

关注	账号	备注
标哥博客iOS交流群一	324400294（满）	群一若已满，请申请群二
标哥博客iOS交流群二	494669518（满）	群二若已满，请申请群三
标哥博客iOS交流群三	461252383（满）	群三若已满，请申请群四
标哥博客iOS交流群四	250351140	群四若已满，会有提示信息
关注微信公众号	iOSDevShares	关注微信公众号，会定期地推送好文章
关注新浪微博账号	标哥的技术博客	关注微博，每次发布文章都会分享到新浪微博
关注标哥的GitHub	CoderJackyHuang	这里有很多的Demo和开源组件
关于我	进一步了解标哥	如果觉得文章对您很有帮助，可捐助我！