Switch branches/tags
Nothing to show
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
..
Failed to load latest commit information.
InsertionSort.playground
Tests
README.markdown
README_en.markdown

README.markdown

插入排序

插入排序动画

目标:把数组从低到高(或从高到低)排序

您将获得按正确的顺序排列一系列数字。插入排序算法的工作原理如下:

  • 把一系列数字放在一个未排序的堆里。
  • 从堆中挑选一个数字。 你选择哪一个并不重要,但从堆顶挑选是最容易。
  • 把这个数插入一个新的数组。
  • 从未排序堆中再选择一个数字,并将其插入之前的数组中。 这个数字在第一个数字之前或之后,所以现在这两个数字被排序。
  • 再从堆中选择一个数字,并将其插入到数组中的正确排序位置。
  • 继续这样做,直到堆里没有数字。 最终得到一个空堆和一个排序的数组。

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

例子

假设这边有需要排序的一些数字 [ 8, 3, 5, 4, 6 ]

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

从堆中选择下一个数字3,然后将其插入到已排序的数组中。 3应该在8之前,所以排序的数组现在是[3,8],而堆被缩减为[5,4,6]

从堆中选择下一个数字5,然后将其插入到已排序的数组中。 5介于38之间。 排序的数组是[3,5,8],堆是[4,6]

重复上面的过程直到堆为空。

原地排序

译注:原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。包括:希尔排序、冒泡排序、插入排序、选择排序、堆排序、快速排序。

上面的解释使你看起来需要两个数组:一个用于存放未排序的堆,另一个用于存放按次序排好的数字。

但您可以执行原地插入排序,而无需创建单独的数组。 您只需追踪数组的哪个部分已经排序,哪个部分是未排序。

最初,数组是[8,3,5,4,6]|条显示已排序部分的结束位置和堆的开始位置:

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

这表明排序的部分是空的,堆开始于8

处理完第一个数字后,结果为:

[ 8 | 3, 5, 4, 6 ]

排好序的部分是[8],未排序的堆是[ 3, 5, 4, 6 ]|条向右移动了一个位置。

下面是排序期间数组内容的变化过程:

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

每一步,|条向右移动一个位置。 如您所见,数组的开始到|部分总是排好序的。堆缩小一位置,排序部分增加一位置,直到堆变为空的,没有更多未排序的数字为止。

怎么插入

每一步,您从未排序堆中选择最顶部的数字,并将其插入到数组的已排序部分。 但必须将该数字插入适当的位置,以便数组的从头开始保持排序。 这是如何运作的?

假设我们已经完成了前几个元素,数组看起来像这样:

[ 3, 5, 8 | 4, 6 ]

要排序的下一个数字是4。 我们需要将它插入到已经排好序的[3,5,8]中。

一种方法是:查看前一个元素8

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

前一个元素比4大吗? 是的,所以4应该在8之前。 我们交换这两个数字得到:

[ 3, 5, 4, 8 | 6 ]
        <-->
        交换

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

[ 3, 4, 5, 8 | 6 ]
     <-->
     交换

再看一下前面的元素。 3大于4吗? 不大于, 这意味着我们完成了数字4保持排序的插入。

下一节将对插入排序算法的内部循环的进行描述,通过交换数字将数字从堆的顶部插入到已排序的部分。

代码

下面插入排序的Swift实现:

func insertionSort(_ array: [Int]) -> [Int] {
    var a = array			 // 1
    for x in 1..<a.count {		 // 2
        var y = x
        while y > 0 && a[y] < a[y - 1] { // 3
            a.swapAt(y - 1, y)
            y -= 1
        }
    }
    return a
}

代码在 playground 里测试:

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

代码工作原理:

  1. 先创建一个数组的拷贝。因为我们不能直接修改参数array中的内容,所以这是非常必要的。insertionSort() 会返回一个原始数组的拷贝,就像Swift已拥有的sort() 方法一样。

  2. 在函数里有两个循环,外循环依次查找数组中的每一个元素;这就是从数字堆中取最上面的数字的过程。变量x是有序部分结束和堆开始的索引(也就是 | 符号的位置)。要记住的是,在任何时候,从0x的位置数组都是有序的,剩下的则是无序的。

  3. 内循环则从 x 位置的元素开始查找。x是堆顶的元素,它有可能比前面的所有元素都小。内循环从有序数组的后面开始往前查找。每次找到一个大的元素,就交换它们的位置,直到内层循环结束,数组的前面部分依然是有序的,有序的元素也增加了一个。

注意: 外层循环是从1开始,而不是0。从堆顶将第一个元素移动到有序数组没有任何意义,可以跳过。

不交换

上面的插入排序算法可以很好的完成任务,但是也可以通过移除对 swap() 的调用来提升速度。

通过交换两个数字来让下一个元素移动到合适的位置的:

[ 3, 5, 8, 4 | 6 ]
        <-->
        swap
        
[ 3, 5, 4, 8 | 6 ]
     <-->
     swap

可以通过将前面的元素往右挪一个位置来代替元素的交换,然后将新的数字放到正确的位置。

[ 3, 5, 8, 4 | 6 ]   remember 4
           *

[ 3, 5, 8, 8 | 6 ]   shift 8 to the right
        --->
        
[ 3, 5, 5, 8 | 6 ]   shift 5 to the right
     --->
     
[ 3, 4, 5, 8 | 6 ]   copy 4 into place
     *

代码:

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array
  for x in 1..<a.count {
    var y = x
    let temp = a[y]
    while y > 0 && temp < a[y - 1] {
      a[y] = a[y - 1]                // 1
      y -= 1
    }
    a[y] = temp                      // 2
  }
  return a
}

//1 这行代码就是将前一个元素往右移动一个位置,在内层循环结束的时候, y 就是 插入的数字 在有序数组中的位置, //2 这行代码就是将数字拷贝到正确的位置。

泛型化

如果能排序的类型不止数字就更好了。我们可以使数组的数据类型泛型化,然后使用一个用户提供的函数(或闭包)来执行比较操作。这只要改变两个地方。

函数签名变成:

译注:函数签名的英文原文是 function signature,而我们常接触到是 函数声明(function declaration),这两个概念都是有的,暂且不去追究它们的区别了,此处就译为函数签名,应该不影响对下面文章的理解。

func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {

数组有一个类型 [T][T] 是泛型化的一个占位类型。现在 insertionSort() 可以接收任何类型的数组,不管它是包含数字、字符串或者其它类型。

新的参数 isOrderedBefore: (T, T) -> Bool 是一个接收两个 T 对象然后返回一个 Bool 值的方法,如果第一个对象大于第二个,那么返回 true,反之则返回 false。这与 Swift 内置的 sort() 方法是一样的。

另外一个变化就是内循环,现在是这样的:

      while y > 0 && isOrderedBefore(temp, a[y - 1]) {

temp < a[y - 1]isOrderedBefore() 替代,不仅可以比较数字,还可以比较各种对象了。

在 playground 中测试:

let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)

<> 决定排序的顺序,分别代表低到高和高到低。

译注:参数isOrderedBefore可以使用<>,是因为在Swift中运算符定义就类似(T, T) -> Bool
Foundation中可以看到不同类型定义了运算符,比如Decimal就定义了<public static func < (lhs: Decimal, rhs: Decimal) -> Bool
Swift文档介绍了Custom Operators可以参考。

当然,我们也可以对其它数据类型排序如字符串:

let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)

也可以是更复杂的对象:

let objects = [ obj1, obj2, obj3, ... ]
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
翻译:Andy Ron
校队:Andy Ron