算法回顾篇：插入排序从理论到实践

• 更多分享：www.catbro.cn

一、前言：

• 我们在上一章节中学习了算法回顾篇：选择排序，本次我们将继续学习插入排序

二、算法介绍

• 简述（从大到小排序）：有1～N个待排序元素
• 注：后面所说的x元素或者y元素及下标为x或者y对应的序列中的元素
• 1、取x(此时x=1)元素作为当前待比较元素；
• 2、令y=x；
• 3、取y-1元素与y元素进行比较，如果y元素大于y-1位置元素，则y元素与y-1元素进行交换；
• 4、判断y是否大于0，如果大于0，则继续重复执行第3步操作；
• 5、判断x+1是否大于序列的长度，如果不大于，则x=x+1；继续执行第2步，否则排序结束
• 从上面可以看出，插叙排序的特点是，带排序元素前面的元素序列是已经排序好的了，所以当x等于序列的最后一个元素的时候且x已经排序好时，此时该序列也就排序完了。

三、代码实现

• 代码如下，里面的SortUtils部分代码请看算法回顾篇：选择排序:

  class InsertSortDemo {
      fun sort(list: Array<Comparable<Any>>) {
          for (i in 1..(list.size - 1)) {
              var j = i;
              while (j > 0 && SortUtils.less(list[j], list[j - 1])) {
                  SortUtils.exchange(list, j, j - 1);
                  j--;
              }
          }
      }
  }
  

• 测试代码：

  fun main(args: Array<String>) {
      var list: Array<String> = arrayOf("S", "O", "R","T", "E", "X","A","M","P","L","E");
      var insertSort = InsertSortDemo();
      var startTime = System.currentTimeMillis();
      insertSort.sort(list as Array<Comparable<Any>>)
      var endTime = System.currentTimeMillis();
      var costTime = endTime - startTime;
      println("花费时间： $costTime")
  }
  

四、总结：

• 插入排序
• 特点：左侧的元素总是顺序的
• 元素交换次数：最少为0（待排序列表为顺序列表）最多为N^2/2次，
• 平均交换次数：N ^2/4次
• 元素比较次数：最好为N-1次（待排序列表为顺序列表），最差为N^2/2次，平均为N^2/4次
• 某些场景下更适合使用插入排序：
  • 1、数组中每个元素距离他的最终位置距离都不远，这样比较次数和交换次数都是相对较少的
  • 2、数组中只有几个元素顺序不对