资讯专栏INFORMATION COLUMN

通过算法了解Swift 3—插入排序

Coding01 / 1527人阅读

摘要:源自泊学技法学习插入排序是最基础的排序算法之一。在理解插入排序的时候,要时刻记住一件事情元素的操作永远只发生在相邻的两个元素之间。不用交换元素的插入排序方法除了使用或之外,还有一种插入排序的手段。

Insertion sort

源自泊学IOS技法学习

插入排序是最基础的排序算法之一。它最核心的思想,由以下几条构成。当我们要对一个值为[1, 5, 6]
的数组从大到小排列时:

把序列的第一个元素想象成一个“子序列”[1],它是已经排序的;

按照既定的排序规则,把由序列的前两个元素构成的“子序列”排序:[5, 1]

之后,读入6,在之前已经排序好的“子序列”中,从右向左逐个和新读入的元素进行比对。如果满足排序规则,就交换已排序数组中的元素和待排序的元素:

[5, 1, 6] 
    ^ 6 > 1 == true
[5, 1, 6] 
    <---> 
     swap
[5, 6, 1]

简单来说,就是不断通过比对,移动待排序元素的位置。直到待排序元素和之前已排序“子序列”全部元素都比对完之后:

[5, 6, 1] 
 ^ 6 > 5 == true 
[5, 6, 1] 
 <---> 
  swap
[6, 5, 1]

新形成的序列就已经是排序好的了。(当然,这里也有一个潜台词,就是如果和子序列中第一个元素比对之后不需要移动,则新添加进来的元素就应该直接添加到子序列末尾);

反复3的操作,当读完所有待排序的元素之后,整个序列就排序完成了。

在理解插入排序的时候,要时刻记住一件事情:元素的操作永远只发生在相邻的两个元素之间。当我们在头脑中执行插入排序时,偶尔会忘记这条,会想着是否存在着跨元素交换的情况,然后就把自己搞晕了。

实现 如何使用?

在实现之前,我们要先考虑下开发者会如何使用这个算法,例如这样:

let a: Array = [1, 5, 6]
insertionSortOf(a)

或者,我们允许用户指定一个排序方法

let a: Array = [1, 5, 6]
insertionSortOf(a, byCriteria: >) // [6, 5, 1]

然后,我们还应该允许对包含任何“可比较”元素的Array进行排序。于是,insertionSort的声明可以是下面这样的。

如何按Swift 3的方式声明
typealias CRITERIA = (T, T) -> Bool
func insertionSortOf( 
        _ coll: Array, 
        byCriteria: CRITERIA = { $0 < $1 }) ->Array

在这个声明里,有以下和Swift 3相关的说明:

首先,我们使用了SE-0048中的新特性,允许在 typealias 中使用泛型参数;

其次,在方法的命名上,我们参考了SE-0023 API设计指南中的要求:

“如果方法中第一个参数和方法名一起形成了一个语法正确的短语,去掉第一个参数的label,并且把参数label放到方法名中”

因此,我们把“表示要排序的集合”使用的介词“of”,从第一个参数名,放到了函数名中。

第三,在Swift 3里,根据SE-0046中的提议,函数的第一个参数不再默认省略label,它将和其他参数一样拥有默认的label行为。因此,如果我们要省略label,必须在参数名前强制使用_
。因此,在声明里,我们需要强制省略第一个参数的label。

第四,根据SE-0023 API设计指南中的要求:

要让方法调用时,形成语法正确的英文短语。因此,我们让第二个表示自定义比较规则的参数名为byCriteria

要为方法中的closure参数设置label。因此,我们没有去掉第二个closure参数的label;

当方法的参数在绝大多数时候使用相同值时,应为它指定默认值。因此,我们让byCriteria的默认行为是按升序排列;

实现insertionSort

按照一开始我们在算法思路中的描述,在insertionSort中添加下面的代码。

首先,只有一个元素的数组是无需排序的,我们直接返回就好:

func insertionSortOf( 
        _ coll: Array, 
        byCriteria: CRITERIA = { $0 < $1 }) -> Array { 
     
    // 1. An array with a single element is ordered 
     guard coll.count > 1 else { 
         return coll 
    }
}

其次,复制一份参数数组,用于在函数内部进行排序:

func insertionSortOf(
        _ coll: Array, 
        byCriteria: CRITERIA = { $0 < $1 }) -> Array { 

    //: #### 1. An array with a single element is ordered
    guard coll.count > 1 else { 
        return coll
    } 
    var result = coll
}

第三,我们从数组中第二个元素开始,通过逐个比对,来不断形成已排序好的子数组:

for x in 1 ..< coll.count { 
    var = x
    let key = result[y]

    print("Get: (key)") 

    // 2. If the key needs to swap in the previous ordered sub array 
    while y > 0 && byCriteria(key, result[y - 1]) { 
          print("-----------------------------") 
          print("Remove: (result[y]) at pos: (y)") 
          print("Insert: (key) at pos: (y - 1)") 
          print("-----------------------------") 

          // 3. Swap the value 
          // The new Swift 3 API: 
          // remove(at:) replaces removeAtIndex
          // You can also use swap(:) instead of remove and insert. 
          result.remove(at: y) 
          result.insert(key, at: y - 1) 
          y -= 1 
     }
}

最后,数组中所有的元素都遍历之后,整个数组就完成排序了,我们直接把排序后的数组返回:

func insertionSortOf(
       _ coll: Array, 
       byCriteria: CRITERIA = { $0 < $1 }) -> Array { 

    guard coll.count > 1 else { 
       return coll 
    } 

    var result = coll 

    for x in 1 ..< coll.count { 
        var y = x 
        let key = result[y] 

        print("Get: (key)") 

        // 2. If the key needs to swap in the previous ordered sub array 
        while y > 0 && byCriteria(key, result[y - 1]) { 
            print("-----------------------------") 
            print("Remove: (result[y]) at pos: (y)") 
            print("Insert: (key) at pos: (y - 1)") 
            print("-----------------------------") 

            // 3. Swap the value 
            // Notice the new Swift 3 API: remove(at:) replaces removeAtIndex 
            // You can also use swap(:) instead of remove and insert 
            result.remove(at: y)
            result.insert(key, at: y - 1) 

           y -= 1 
       }
    } 
    // 4. Return the sorted array 
return result
}
测试

用一开始我们设计的使用方法来测试insertionSort

let a: Array = [1, 5, 6]
insertionSortOf(a)

由于默认就是从小到大排序,并且,原始数组本身就是已经排序的,因此,我们可以在控制台看到下面的结果:

如果我们传递一个自定义的比较规则,例如从大到小排序:

let a: Array = [1, 5, 6]
insertionSortOf(a, byCriteria: >)

就可以在控制台看到这样的结果:

数字5经历了一次交换,数字6经历了两次交换。

Have a try? 不用交换元素的插入排序方法

除了使用remove&insertswap之外,还有一种插入排序的手段。用之前的[1, 5, 6]降序排列举例。假设算法执行到了读入数字6:

记录读入的值:

[5, 1, 6] 
       ^ --> remember 6

在新读入位置前已排序好的子数组里,不断用前一个数字覆盖后一个位置,为新读入的元素找到合适的位置:

[5, 1, 1]
     --> shift 1 right
[5, 5, 1] 
     --> shift 5 right
[6, 5, 1] 
 ^ --> Copy 6 here

不同的实现方法之间的性能差异有多大呢?

insert&remove

swap

以及我们最后提到的移动元素;

当移动大量元素时,这些算法之间的差异有多大呢?自己试验一下吧,欢迎大家把实验的结果贴到泊学视频下面的泊学Disqus论坛里。 :-)

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/16357.html

相关文章

  • 路由 - 收藏集 - 掘金

    摘要:接下来会发布关于全景视频播放器文章,现在主要是在封装播放器一文件组件化路由设计思路分析掘金前言随着用户的需求越来越多,对的用户体验也变的要求越来越高。 iOS 模式详解—「runtime 面试、工作」看我就 ? 了 ^_^. - iOS - 掘金Write in the first【写在最前】 对于从事 iOS 开发人员来说,当提到 runtime时,我想都可以说出来 「runtime...

    philadelphia 评论0 收藏0
  • 即将立秋的《课多周刊》(第2期)

    摘要:即将立秋的课多周刊第期我们的微信公众号,更多精彩内容皆在微信公众号,欢迎关注。若有帮助,请把课多周刊推荐给你的朋友,你的支持是我们最大的动力。课多周刊机器人运营中心是如何玩转起来的分享课多周刊是如何运营并坚持下来的。 即将立秋的《课多周刊》(第2期) 我们的微信公众号:fed-talk,更多精彩内容皆在微信公众号,欢迎关注。 若有帮助,请把 课多周刊 推荐给你的朋友,你的支持是我们最大...

    ruicbAndroid 评论0 收藏0
  • 即将立秋的《课多周刊》(第2期)

    摘要:即将立秋的课多周刊第期我们的微信公众号,更多精彩内容皆在微信公众号,欢迎关注。若有帮助,请把课多周刊推荐给你的朋友,你的支持是我们最大的动力。课多周刊机器人运营中心是如何玩转起来的分享课多周刊是如何运营并坚持下来的。 即将立秋的《课多周刊》(第2期) 我们的微信公众号:fed-talk,更多精彩内容皆在微信公众号,欢迎关注。 若有帮助,请把 课多周刊 推荐给你的朋友,你的支持是我们最大...

    MRZYD 评论0 收藏0
  • 即将立秋的《课多周刊》(第2期)

    摘要:即将立秋的课多周刊第期我们的微信公众号,更多精彩内容皆在微信公众号,欢迎关注。若有帮助,请把课多周刊推荐给你的朋友,你的支持是我们最大的动力。课多周刊机器人运营中心是如何玩转起来的分享课多周刊是如何运营并坚持下来的。 即将立秋的《课多周刊》(第2期) 我们的微信公众号:fed-talk,更多精彩内容皆在微信公众号,欢迎关注。 若有帮助,请把 课多周刊 推荐给你的朋友,你的支持是我们最大...

    K_B_Z 评论0 收藏0
  • JS中可能用得到的全部的排序算法

    本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法,文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现,如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读 排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...

    verano 评论0 收藏0

发表评论

0条评论

Coding01

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<