声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流

插入排序算法的目的：将一个无序数组按照升序或者降序排列起来。

当你得到一个无序数组，并需要将该数组按照需求进行排序时，插入排序算法会按照以下步骤执行实现：

1.将所有数字放在一起，我们假设此时所有的数字被无序但又整齐的排列在一个通道上。
2.从通道上随意取出一个数字，可以从最前端取，也可以从最后端去，无所谓。不过最简单的每次都从最前端取出。
3.将取出来的数字放入新的数组里面。
4.从通道中取出第二个数字并且插入第三步建立的新数组里面，根据升降序将新数字放在第一个数字的前面或者后面，得到一个有顺序的数组。
5.继续从通道中取出新数字，根据大小插入到新数组合适的位置。
6.重复以上步骤直到通道中没有数字，排序完毕，新的数组就是我们得到的排序好的数组。

例子

我们需要整理一个无序数组为［8，3，5，4，6］。
取出第一个数字8，得到新的数组［8］。无序数组变为［3，5，4，6］。
取出第二个数字3，插入新的数组里，3比8小，得到［3，8］。无序数组变为［5，4，6］。
取出第三个数字5，插入新的数组里，5比3大，比8小，得到［3，5，8］。无序数组变为［4，6］。
取出第四个数字4，插入新的数组里，4比3大，比5小，得到［3，4，5，8］。无序数组变为［6］。
最后取出6，插入新数组里，6比5大，比8小，得到［3，4，5，6，8］。排序完成。

原地排序

我们刚才对插入排序算法的解释，可能会让大家误以为插入排序必须要有两个数组配合完成，一个放无序数组，一个为有序数组。其实不然，我们可以对一个无序数组直接进行原地排序，不需要多建一个数组。这里我们需要注意的就是区分开数组里已排序和未排序的部分。

还是刚才的数组［8，3，5，4，6］。这次我们用｜来划分数组中已排序和未排序。

［ ｜8，3，5，4，6］

我们从左向右开始整理数组，｜放在最前面，此时已整理部分为空。当我们开始向右移动｜，我们得到

［ 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］。先将｜向右移动一个位置，让4进入左侧区域，此时，我们将4与其左侧数字8（已排序好数组里最大的）进行比较：

［ 3，5，8，4｜6 ］
           ^

4比8小，所以4应该在8前面，将两个数字交换位置：

［ 3，5，4，8｜6 ］
        <-->
        交换

我们继续4和左侧数字5进行对比，4比5小，所以4应该在5前面，继续交换位置：

［ 3，4，5，8｜6 ］
     <-->
     交换

再次对比4和左侧数字3，4比3大，不需要交换位置，此时左侧数组又变成排序好的数组。

以上过程为插入排序算法的内循环描述，在下一部分的代码中会体现出来。总体过程就是将右侧数值放入左侧已排序数组的最右端，然后通过大小比较不断地交换位置，直到结束。

代码

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
      swap(&a[y - 1], &a[y])
      y -= 1
    }
  }
  return a
}

可以将上述代码放在playground并进行以下测试：

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

代码的运行逻辑如下：

1.首先复制整个数组。这个步骤是必须的因为我们不能直接对原始数组的内容进行修改。就像Swift自己的函数sort()，insertionSort()只会返回一个整理好的原始数组的复制数组。

2.整个函数有两个循环。外部循环按照顺序遍历数组里的每一个数字，同时每次外部循环所选择的数字，就是每次｜向右侧移动进来的数字。这里x表示左侧已排序数组最后一位数字的位置，记住，数组里从0到x的部分就是已经排序好的部分。其余的为未排序的部分。

3.内部循环从位于x位置的数字，也就是从｜向右移动进来的数字，开始不断向前一位进行大小比较，当发现当前位置的数字小于前一位，立刻向左移动并继续比较，直到排序结束。

去掉交换过程

上述版本的代码运行效果良好，但是，我们仍然可以进行优化，方法就是去掉swap()方程。你已经知道我们需要将顺序不对的数字进行位置调整：

［ 3，5，4，8｜6 ］
        <-->
        交换
［ 3，4，5，8｜6 ］
     <-->
     交换

去掉图中的交换过程，我们可以将图中需要交换位置的数字直接向右移动，然后将新的数字直接复制到正确的位置：

[ 3，5，8，4｜6 ]   记住4
          ＊

[ 3，5，8，8｜6 ]  将8转移到右侧
        -->

[ 3，5，5，8｜6 ]  将5转移到右侧
     -->

[ 3，4，5，8｜6 ]  将4复制粘贴到新的位置
     ＊

代码如下：

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就是将新数字复制到该位置。

通用化

很显然，上述的代码只适合对数字类型的数据进行排序，但这里我们只需要对代码进行两处修改，即可完成对大部分类型数据的排序。首先，函数名更改如下：

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

此时数组的数据类型为[T]，这里的T是通用类型，可以是数值，字符串，或者其他数据类型。新的参数isOrderedBefore: (T, T) -> Bool函数带有两个T对象，函数返回true表示第一个对象排在第二个对象前面，返回false则表示第一个对象排在第二个对象后面。效果等同于Swift自带函数sort()。

第二个修改的地方是内循环:

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

这里我们用isOrderedBefore()取代了temp < a[y - 1]，它们的目的相同，唯一不一样的是前者可以对任何数据类型进行比较，不单单是数字。

我们可以在playground进行以下测试:

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

这里<和>表示序列的顺序，从小到大或者从大到小。当然我们也可以对其他数据类型进行排序，比如字符：

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

或者是更复杂的对象：

let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }

这里的闭环告诉insertionSort()函数对对象的priortity特性进行排序。

插值排序属于稳定排序。当数组里含有同样的整理参考对象的元素在经过整理后仍然保持原来的顺序，我们就说这个排序就是稳定的。这个特性对于数值或者字符排序来说并不是很重要，但是对于更复杂的对象来说就非常重要了。正如上面的例子，如果数组里面的两个对象拥有同样的priority，我们可以无视掉它们的其它特性值，不对它们进行位置的调整。

性能

当数组是已经排序好的数组，插值排序算法的运行速度非常快。这句话听起来好像理所当然，但是对于所有搜索算法来说，并不是这样的。实际上，在大部分数据已经排序好的前提下，不是全部，插值排序依然可以取得不赖的效果。

对于插值排序算法来说，O(n^2)是它最差和平均性能表现。因为它的函数里含有两个循环。其它类型的排序算法，比如快速排序和归并排序，在输入数据量很大的情况下，可以达到O(nlogn)的效果。

插值排序对于小数据量的排序来说非常快。在一些标准程序库里，如果数据大小不大于10，它们会用插值排序来取代快速排序。