目录

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


一、前言:
二、算法介绍
  • 简述(从大到小排序):有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、数组中只有几个元素顺序不对