UDN-企业互联网技术人气社区

板块导航

浏览  : 1099
回复  : 0

[其它] Swift算法俱乐部中文版 -- 插入排序

[复制链接]
哥屋恩的头像 楼主
发表于 2016-11-6 13:14:41 | 显示全部楼层 |阅读模式
  目标:从小到大(或从大到小)对数组进行排序。

  给你一组数组,将他们排序。插入排序算法的步骤如下:

  把未排序的数字放在一堆。

  从这堆数字里面挑一个。选哪个并不重要,但从顶部拿最容易。

  将选出来的数字插入新数组中。

  从未排序的数字堆中挑一个数字,并将其插入新数组。 在您选择的第一个数字之前或之后,将这两个数字排序。

  再选择一个数字,并按顺序插入到数组中适当的位置。

  重复这样做,直到堆里没有数字。 你最终得到一个空堆和一个排序的数组。

  这就是为什么这被称为“插入”排序,因为你从堆中取一个数字,并将其插入在数组里正确的排序位置。

7.jpeg


  我们摸扑克牌就是插入排序!

  举个栗子

  未排序的数字堆是 [ 8, 3, 5, 4, 6 ] 。

  选择第一个数字 8 ,并将其插入新数组。 新数组是空的,所以很容易。 排序的数组现在是 [8] ,未排序的堆是 [ 3, 5, 4, 6 ] 。

  从堆中选择下一个数字 3 ,并将其插入到排序的数组中。 它应该在8之前,所以排序的数组现在 [ 3, 8 ] ,堆是 [ 5, 4, 6 ] 。

  从堆中选择下一个数字5,并将其插入到排序的数组中。 它在3和8之间。排序的数组是 [ 3, 5, 8 ] ,堆是 [ 4, 6 ] 。

  重复此过程,直到堆是空的。

  在一个数组中排序

  上面的解释会你看起来需要两个数组:一个用于未排序的数组,一个排序好的数组。

  但是你可以在一个数组里执行插入排序,而无需创建新的数组。 你只需知道数组的哪个部分已经排序,哪个部分是未排序的堆。

  最初,数组是 [ 8, 3, 5, 4, 6 ] 。用 | 区别排序部分和未排序部分:

 
  1.  [| 8, 3, 5, 4, 6 ]
复制代码

  这表示排序部分是空的,未排序的数字堆从8开始。

  处理完第一个数字后,是这样的:

 
  1.  [ 8 | 3, 5, 4, 6 ]
复制代码


  排序部分是 [ 8 ] ,堆是 [ 3, 5, 4, 6 ] 。 | 已经向右移位了一位。

  这是数组的排序过程:

  1.   [| 8, 3, 5, 4, 6 ]

  2.   [ 8 | 3, 5, 4, 6 ]

  3.   [ 3, 8 | 5, 4, 6 ]

  4.   [ 3, 5, 8 | 4, 6 ]

  5.   [ 3, 4, 5, 8 | 6 ]

  6.   [ 3, 4, 5, 6, 8 |]
复制代码


  在每个步骤中,| 从数组的开头,一下一下的向后移动,直到排序完成时到达数组的结尾。 数字堆一个个缩小,并且排序部分一个个增加,直到数字堆是空的,并且所有数字都排序完成。

  怎样插入?

  每个步骤,都要从未排序的堆中选择最顶层的数字,并将其插入排序数组。 您必须把数字放在合适的位置,保证数组是排序好的。 怎样做呢?

  我们假设已经做了几步,数组看起来像这样:

 
  1.  [ 3, 5, 8 | 4, 6 ]
复制代码

  下一个要排序的数字是 4 ,排序好的部分是 [ 3, 5, 8 ] 。

  用这种方法:看看上一个元素 8 。

  1.   [ 3, 5, 8, 4 | 6 ]

  2.   ^
复制代码


  8 是否大于 4 ? 是的,所以 4 应该在 8 之前。我们交换这两个数字得到:

  1.   [ 3, 5, 4, 8 | 6 ]

  2.   <-->

  3.   交换
复制代码


  还没完。 新的前一个元素 5 也大于 4 。我们还交换这两个数字:

  1.   [ 3, 4, 5, 8 | 6 ]

  2.   <-->

  3.   交换
复制代码

  再看看前面的元素。 3 大于 4 吗? 不是。 这意味着我们完成了 4 在数组中的排序。

  这是插入排序算法,您将在下一节中看到内部循环的描述部分:通过交换数字将从堆的顶部的数字插入到排序的部分。

6.gif


  代码

  这是用 Swift 实现的插入排序:

  1.   func insertionSort(_ array: [Int]) -> [Int] {

  2.   var a = array // 1

  3.   for x in 1..

  4.   var y = x

  5.   while y > 0 && a[y] < a[y - 1] { // 3

  6.   swap(&a[y - 1], &a[y])

  7.   y -= 1

  8.   }

  9.   }

  10.   return a

  11.   }
复制代码


  把这段代码放到 playground 里测试:

  1.   let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]

  2.   insertionSort(list)
复制代码


  注释对应的代码分析:

  创建数组的副本。这是必要的,因为我们不能直接修改参数 array 的内容。 像Swift 中的 sort()一样,insertionSort() 函数将返回原始数组的副本,并将它排序。

  这个函数里有两个循环:外部循环遍历数组中的每个元素,从数字堆的最顶端挑选数字;变量 x 是排序区分排序不分与数字堆的索引(相当于 | 的作用)。请记住,任何时候,array[0] 到 array[x] 都是排序完成的。从 array[x] 到结束,是未排序的数字堆。

  循环查看 array[x] ,这是在数字堆中顶部的数组,它可能小于排序数组的任何元素。循环排序好的数组,每次往前找一个,如果前面的更大,就交换它们。当循环完成时,排序好的数组就增长了一个元素。

  注意:外循环从(注释2处)索引从1开始,将第一个元素从数字堆中移动到排序部分并不会改变任何内容,所以我们可以跳过它。

5.gif


  减少交换

  上面的插入排序虽然能使用,但是如果能删除 swap() 方法会运行的更快。

  您已经看到,我们交换数字,将下一个元素根据排序移动到合适的位置:

  1.   [ 3, 5, 8, 4 | 6 ]

  2.   <-->

  3.   swap

  4.   [ 3, 5, 4, 8 | 6 ]

  5.   <-->

  6.   swap
复制代码


  我们可以不交换,将数字向右移动,然后把新数字放到合适的位置就可以了。

  1.   [ 3, 5, 8, 4 | 6 ] 复制 4

  2.   *

  3.   [ 3, 5, 8, 8 | 6 ] 将 8 向右移动

  4.   --->

  5.   [ 3, 5, 5, 8 | 6 ] 将 5 向右移动

  6.   --->

  7.   [ 3, 4, 5, 8 | 6 ] 把 4 粘贴到合适的位置

  8.   *
复制代码


  代码:

  1.   func insertionSort(_ array: [Int]) -> [Int] {

  2.   var a = array

  3.   for x in 1..

  4.   var y = x

  5.   let temp = a[y]

  6.   while y > 0 && temp < a[y - 1] {

  7.   a[y] = a[y - 1] // 1

  8.   y -= 1

  9.   }

  10.   a[y] = temp // 2

  11.   }

  12.   return a

  13.   }
复制代码


  // 1 处是将数字向右移动一位。内循环结束时,y 是排序数组中和新数字比较的索引。// 2 处是将新数字复制到对应的位置。

  给其他类型排序

  我们可以给其他类型排序,添加泛型并提供比较函数即可。只需要修改两处代码。

  方法定义变为:

 
  1.  func insertionSort(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
复制代码


  数组具有泛型 [T],现在 isOrderedBefore() 方法将接受任何类型,无论是数组,字符串,或是其他类型。

  新的参数 isOrderedBefore: (T, T) -> Bool 是一个方法 ,接受两个 T 类型的对象,如果两个参数比较厚满足这个表达式,返回 true,不满足则返回 false。就像是 Swift 内置的 sort() 方法。

  另一个改动的地方是在内循环:

 
  1.  while y > 0 && isOrderedBefore(temp, a[y - 1]) {
复制代码

  将 temp < a[y - 1] 替换为 isOrderedBefore() 方法。它做了同样的事情,并且可以比较任何类型。

  在 Playground 中测试:

  1.   let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]

  2.   insertionSort(numbers, <)

  3.   insertionSort(numbers, >)
复制代码


  < 和 > 决定排序顺序,分别是从小到大和从大到小。

  当然,你也可以排序其他类型,如字符串:

  1.   let strings = [ "b", "a", "d", "c", "e" ]

  2.   insertionSort(strings, <)
复制代码


  甚至是更复杂的对象:

 
  1.  let objects = [ obj1, obj2, obj3, ... ]

  2.   insertionSort(objects) { $0.priority < $1.priority }
复制代码

  闭包是告诉 insertionSort() 根据对象的属性 priority 进行排序。

  插入排序是一种稳定的排序。对于都具有排序键的元素,是相对稳定的。这对于简单的数字或字符串不重要 ,但对于复杂对象就非常重要了。在上面的例子中,两个对象的 priority 一样的话,就不会交换,不管其他属性的值多大多小。

  性能

  如果数组已经排序,那插入排序真的很快。这听起来很明显,但不是所有的排序算法都能做到。在实践中,如果是大量数据并不完全排序,插入排序会表现的很好。

  最坏情况下插入排序的平均情况性能是 O(n ^ 2) 。 这是因为在这个函数中有两个嵌套循环。 其他排序算法(如快速排序和合并排序)的性能是 O(n log n),在数据量较大时更快。

  插入排序实际上对排序小数组非常快。 当元素个数为10或更小需要排序的时候,一些标准库会把它们的排序方法从快速排序切换到插入排序。

  我做了一个简单的测试比较我们的 insertionSort() 与 Swift 的内置 sort() 。 在大约100个元素左右的数组上,速度的差异很小。 然而,随着个数增加,O(n ^ 2) 很快开始执行比 O(n log n) 差很多,并且插入排序不能跟上。

  作者:Matthijs Hollemans -- Swift 算法俱乐部

  英文链接:

  https://github.com/raywenderlich ... er/Insertion%20Sort

原文作者:云抱住阳光太阳没放弃发亮   来源:开发者头条

相关帖子

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部