插入排序算法讲解及swift代码实现

2018-09-1015:16:52数据结构与算法Comments2,510 views字数 3037阅读模式

插入排序算法讲解

插入排序的基本思想是:从数组中拿出一个元素(通常就是第一个元素)以后,再从数组中按顺序拿出其他元素。如果拿出来的这个元素比这个元素小,就放在这个元素左侧;反之,则放在右侧。整体上看来有点和玩儿扑克牌的时候将刚拿好的牌来做排序差不多。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

插入排序也是两层循环:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

  • 外层循环的边界是[1,array.count),index为i。
  • 内层循环开始的时候初始index j = i,然后使用一个while循环,循环条件是j>0 && array[j] < array[j - 1],循环内侧是交换j-1和j的元素,并使得j-1。可以简单理解为如果当前的元素比前一个元素小,则调换位置;反之进行下一个外层循环。

下面我们还是用手写迭代的方式看一下插入排序的机制,使用的数组和上面选择排序的数组一致:[4, 1, 2, 5, 0]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

i = 1 时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

  1. j = 1:array[1] < array[0], 交换4和1:[1, 4, 2, 5, 0],j-1之后不符合内层循环条件,退出内层循环,i+1。

i = 2 时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

  1. j = 2,array[3] < array[2],交换4和2:[1, 2, 4, 5, 0],j向左移动,array[2] > array[1],不符合内层循环条件,退出内层循环,i+1。

i = 3 时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

  1. j = 3,array[3] > array[2],不符合内层循环条件,退出内层循环,i+1。

i = 4 时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

  1. j = 4,array[4] < array[3],交换5和0:[1, 2, 4, 0, 5],j -1。
  2. j = 3,array[3] < array[2],交换4和0:[1, 2, 0, 4, 5],j -1。
  3. j = 2,array[2] < array[1],交换4和0:[1, 0, 2, 4, 5],j -1。
  4. j = 1,array[1] < array[0],交换1和0:[0, 1, 2, 4, 5],j -1 = 0,不符合内层循环条件,退出内层循环,i+1 = 5,不符合外层循环条件,排序终止。

从上面的描述可以看出,和选择排序相比,插入排序的内层循环是可以提前推出的,其条件就是array[j] >= array[j - 1],也就是说,当前index为j的元素只要比前面的元素大,那么该内层循环就立即退出,不需要再排序了,因为该算法从一开始就是小的放前面,大的放后面。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

代码实现

下面我们通过代码来看一下如何实现插入排序算法:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

func insertionSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 1..<array.count {
        
        var j = i
        while j > 0 && array[j] < array[j - 1] {
             array.swapAt(j - 1, j)
            j -= 1
        }
    }
    return array
}
复制代码

从上面的代码可以看出插入排序内层循环的条件:j > 0 && array[j] < array[j - 1]。只要当前元素比前面的元素小,就会一直交换下去;反之,当大于等于前面的元素,就会立即跳出循环。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

之前笔者有提到相对于选择排序,说插入排序可以减少元素之间对比的次数,下面我们通过打印对比次数来对比一下两种算法:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

使用元素个数为50,最大值为50的随机数组:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

selection sort...
compare times:1225
selection sort time duration : 178ms

insertion sort...
compare times:519
insertion sort time duration : 676ms
复制代码

我们可以看到,使用选择排序的比较次数比插入排序的比较次数多了2倍。但是遗憾的是整体的性能选择排序要高于插入排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

也就是说虽然插入排序的比较次数少了,但是交换的次数却比选择排序要多,所以性能上有时可能不如选择排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

注意,这不与笔者之前的意思相矛盾,笔者只是说在减少比较次数上插入排序是优于选择排序的,但没有说插入排序整体上优于选择排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

那么有何种特性的数组可以让排序算法有其用武之地呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

从上面使用插入排序来排序[4, 1, 2, 5, 0]这个数组的时候,我们可以看到,因为0这个元素已经在末尾了,所以在j=4的时候我们费了好大劲才把它移到前面去。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

那么将这个情况作为一个极端,我们可以这样想:如果这个数组里的元素里的index大致于最终顺序差不多的情况是不是就不用做这么多的搬移了?。这句话听起来像是理所当然的话,但是有一种数组属于“基本有序”的数组,这种数组也是无需的,但是它在整体上是有序的,比如:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

[2,1,3,6,4,5,9,7,8]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

用笔者的话就叫做整体有序,部分无序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

我们可以简单用这个数组来分别进行选择排序和插入排序做个比较:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

selection sort...
compare times:36
selection sort time duration : 4.7ms

insertion sort...
compare times:5
insertion sort time duration : 3.2ms
复制代码

我们可以看到插入排序在基本有序的测试用例下表现更好。为了让差距更明显,笔者在Array+Extension.swift文件里增加了一个生成基本有序随机数组的方法:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

static public func nearlySortedArray(size: Int, gap:Int) -> [Int] {

    var result = [Int](repeating: 0, count:size)

    for i in 0 ..< size {
        result[i] = i
    }

    let count : Int = size / gap
    var arr = [Int]()

    for i in 0 ..< count {
        arr.append(i*gap)
    }

    for j in 0 ..< arr.count {
        let swapIndex = arr[j]
        result.swapAt(swapIndex,swapIndex+1)
    }

    return result
}
复制代码

该函数需要传入数组的长度以及需要打乱顺序的index的跨度,它的实现是这样子的:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

  • 首先生成一个完全有序的序列。
  • 将数组长度除以跨度来得出需要交换的index的个数count。
  • 根据这个count可以得出需要交换的index,把这些index放在一个新的arr里面
  • 便利这个arr来取出index,将之前生成好的w安全有序的数组的index于index+1做交换。

举个例子,如果我们生成一个数组长度为12,跨度为3的基本有序的数组,就可以这么调用:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

var originalArray = Array<Int>.nearlySortedArray(size: 12, gap: 3)
//[1, 0, 2, 4, 3, 5, 7, 6, 8, 10, 9, 11]
复制代码

跨度为3,说明有12/3 = 4 - 1 = 3 个元素需要调换位置,序号分别为0,3,6,9。所以序号为0,1;3,4;6,7;9,10的元素被调换了位置,可以看到调换后的数组还是基本有序的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

现在我们可以用一个比较大的数组来验证了:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

var originalArray = Array<Int>.nearlySortedArray(size: 100, gap: 10)
复制代码

结果为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

selection sort...
compare times:4950
selection sort time duration : 422ms

insertion sort...
compare times:10
insertion sort time duration : 56.4ms
复制代码

我们可以看到差距是非常明显的,插入排序的性能是选择排序的性能的近乎10倍。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4507.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/4507.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定