选择排序算法讲解及swift代码实现

2018-09-1015:15:36数据结构与算法Comments2,386 views字数 3625阅读模式

选择排序算法讲解

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

  • 外层循环的边界是[0,array.count-1),index为i。
  • 内层循环的边界是[i+1,array.count),index为j。可以看到内层的范围也是不断缩小的,而且范围的前端一直后移,后端保持不变。

具体做法是:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

  • 在外层循环的开始,将i作为最小值index(很可能不是该数组的最小值)。
  • 在内层循环里面找到当前内层循环范围内的最小值,并与已经记录的最小值作比较:
    • 如果与当前记录的最小值index不同,则替换
    • 如果与当前记录的最小值index相同,则不替换

我们还是用手写迭代的方式看一下选择排序的机制,使用的数组和上面交换排序和冒泡排序(非优化版)的数组一致:[4, 1, 2, 5, 0]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

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

  1. 记录当前的最小值的index为0,当前最小值为4。
  2. 内层循环开始,找到[1,5)之间的最小值为0,0的index为4,与当前最小值的index0不同,所以二者要做交换。交换后的数组:[0, 1, 2, 5, 4]。当前内层循环结束,i++。

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

  1. 记录当前的最小值的index为1,当前最小值为1。
  2. 内层循环开始,找到[2,5)之间的最小值为1,与当前记录的最小值index相同。也就是说后面没有比1还要小的了,不做交换。当前内层循环结束,i++。

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

  1. 记录当前的最小值的index为2,当前最小值为2。
  2. 内层循环开始,找到[3,5)之间的最小值为2,与当前记录的最小值index相同。也就是说后面没有比1还要小的了,不做交换。当前内层循环结束,i++。

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

  1. 记录当前的最小值的index为3,当前最小值为2。
  2. 内层循环开始,找到[4,5)之间的最小值为4,4的index为4,与当前记录的最小值index3不同,所以二者要做交换。交换后的数组:[0, 1, 2, 4, 5]。当前内层循环结束,i++。

i = 4 时:不符合外层循环的边界条件,不进行外层循环,排序结束。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

我们可以看到,同样的初始序列,使用选择排序只进行了2次交换,因为它知道需要替换的最小值是什么,做了很少没意义的交换。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

代码实现

我们用代码来实现一下上面选择排序的算法:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

func selectionSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }

    for i in 0 ..< array.count - 1{
        
        var min = i
        
        for j in i + 1 ..< array.count {
            
            if array[j] < array[min] {
                min = j 
            }
        }
        
        //if min has changed, it means there is value smaller than array[min]
        //if min has not changed, it means there is no value smallter than array[min]
        if i != min {
            array.swapAt(i, min) 
        }
    }
    return array
}
复制代码

从上面的代码可以看到,在这里使用了min这个变量记录了当前外层循环所需要被比较的index值,如果当前外层循环的内层循环内部找到了比这个最小值还小的值,就替换他们。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

下面我们使用log来看一下此时选择排序作替换的次数:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

original array:
[4, 1, 2, 5, 0]

advanced bubble sort...
after swap: [1, 4, 2, 5, 0]
after swap: [1, 2, 4, 5, 0]
after swap: [1, 2, 4, 0, 5]
after swap: [1, 2, 0, 4, 5]
after swap: [1, 0, 2, 4, 5]
after swap: [0, 1, 2, 4, 5]

selection sort...
after swap: [0, 1, 2, 5, 4]
after swap: [0, 1, 2, 4, 5]
复制代码

从上面的log可以看出二者的对比应该比较明显了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

为了进一步验证选择排序的性能,笔者在网上找到了两个工具:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

  • 计算程序运行时间的类:executionTimeInterval.swift
  • 生成各种类型随机数的Array的分类:Array+Extension.swift

首先看executionTimeInterval.swift的实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

//time interval
public func executionTimeInterval(block: () -> ()) -> CFTimeInterval {
    let start = CACurrentMediaTime()
    block();
    let end = CACurrentMediaTime()
    return end - start
}


//formatted time
public extension CFTimeInterval {
    public var formattedTime: String {
        return self >= 1000 ? String(Int(self)) + "s"
            : self >= 1 ? String(format: "%.3gs", self)
            : self >= 1e-3 ? String(format: "%.3gms", self * 1e3)
            : self >= 1e-6 ? String(format: "%.3gµs", self * 1e6)
            : self < 1e-9 ? "0s"
            : String(format: "%.3gns", self * 1e9)
    }
}
复制代码

第一个函数以block的形式传入需要测试运行时间的函数,返回了函数运行的时间。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

第二个函数是CFTimeInterval的分类,将秒数添加了单位:毫秒级的以毫秒显示,微秒级的以微秒显示,大于1秒的以秒单位显示。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

使用方法是:将两个swift文件拖进playground里面的Sources文件夹里,并点击二者后,进入playground内部:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

var selectionSortedArray = [Int]()
var time4 = executionTimeInterval{
    selectionSortedArray = selectionSort(&originalArray4) //要测试的函数
}

print("selection sort time duration : \(time4.formattedTime)") //打印出时间
复制代码

再来看一下Array+Extension.swift类:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

先介绍其中的一个方法,生成随机数组:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

import Foundation

extension Array {
    
    static public func randomArray(size: Int, maxValue: UInt) -> [Int] {
        var result = [Int](repeating: 0, count:size)
        
        for i in 0 ..< size {
            result[i] = Int(arc4random_uniform(UInt32(maxValue)))
        }
        
        return result
    }
}
复制代码

这个方法只需要传入数组的大小以及最大值就可以生成一个不超过这个最大值的随机数组。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

比如我们要生成一个数组长度为10,最大值为100的数组:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

var originalArray = Array<Int>.randomArray(size: inputSize, maxValue:100)
//originalArray:[87, 56, 54, 20, 86, 33, 41, 9, 88, 55]
复制代码

那么现在有了上面两个工具,我们就可以按照我们自己的意愿来生成测试用例数组,并且打印出所用算法的执行时间。我们现在生成一个数组长度为10,最大值为100的数组,然后分别用优化的冒泡排序和选择排序来看一下二者的性能:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

original array:
[1, 4, 80, 83, 92, 63, 83, 23, 9, 85]

advanced bubble sort...
advanced bubble sort result: [1, 4, 9, 23, 63, 80, 83, 83, 85, 92] time duration : 8.53ms

selection sort...
selection sort result: [1, 4, 9, 23, 63, 80, 83, 83, 85, 92] time duration : 3.4ms
复制代码

我们现在让数组长度更长一点:一个长度为100,最大值为200:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

advanced bubble sort...
advanced bubble sort sorted elemets: 100 time duration : 6.27s

selection sort...
selection sort sorted elemets: 100 time duration : 414ms
复制代码

可以看到,二者的差别大概在12倍左右。这个差别已经很大了,如果说用选择排序需要1天的话,冒泡排序需要12天。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

现在我们学习了选择排序,知道了它是通过减少交换次数来提高排序算法的性能的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

但是关于排序,除了交换操作以外,对比操作也是需要时间的:选择排序通过内层循环的不断对比才得到了当前内层循环的最小值,然后进行后续的判断和操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4506.html

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

Comment

匿名网友 填写信息

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

确定