插入排序（Kotlin）

目标：将一个数组按照从低到高（或者从高到低）的顺序排序。
插入排序就是给定一个包含数字的数组，需要将它们放到正确的顺序。插入排序算法按照以下步骤运行：

• 将所有的数字放到一个堆。这个堆中的数据是未排序的。
• 从堆中取一个数字。具体取哪一个数字并不重要，但是最简单的方式是取堆顶部的那一个数字。
• 将这个数字插入到新的数组中。
• 从未排序的堆中取下一个数字同样插入到新的数组。它会被插入到第一个数字的左边或者右边，现在这两个数字是有序的。
• 继续取下一个数字并将它插入到新的数组合适的位置。
• 如此循环直到堆中的数字都取完。最终留下一个空的堆和一个排序好的数组。

这就是为什么这个算法被称为“插入”排序。因为我们是从一个堆中取出数字并将它插入到已排序数组中合适的位置。

示例

假设现在需要排序的数字是 [ 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 ]。用| 竖线标识了已排序数组的终点和未排序堆的起点：

[| 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 大吗？是，所以它应该在 8 的前面。我们交换这两个元素：

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

现在还没有完成，现在它前面的元素是 5，它也比 4 大，我们同样交换这两个元素的位置：

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

继续查看前一个元素，3 比 4 要小。这意味着我们已经将 4 放入了合适的位置。现在竖线左侧的数字又变成了有序的。

这就是插入排序算法内部循环的描述，具体的代码实现我们在下一节再讨论。它通过交换元素位置来实现将堆顶部的数字插入到数组中已排序的部分。

代码实现

下面是 Kotlin 实现的一个插入排序

class InsertionSort {

    fun insertSort(sourceArray: IntArray): IntArray {
        val resultArray = sourceArray.clone()                          //1
        for (i in 1 until resultArray.size) {                          //2
            var y = i
            while (y > 0 && resultArray[y] < resultArray[y - 1]) {     //3
                swap(resultArray, y - 1, y)
                y--
            }
        }
        return resultArray
    }


    private fun swap(array: IntArray, start: Int, end: Int) {
        val temp = array[start]
        array[start] = array[end]
        array[end] = temp
    }
}

添加一段测试代码来验证一下：

@Test
    fun insertSort() {
        val sorter = InsertionSort()

        val emptyList = intArrayOf()
        assertEquals(emptyList.clone().apply{ sort() }.joinToString(),
                sorter.insertSort(emptyList).joinToString())

        val listWithOneElement = intArrayOf(23)
        assertEquals(listWithOneElement.clone().apply { sort() }.joinToString(),
                sorter.insertSort(listWithOneElement).joinToString())

        val list = intArrayOf(10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26)
        assertEquals(list.clone().apply { sort() }.joinToString(),
                sorter.insertSort(list).joinToString())
    }

来看一看代码是怎么运行的。

1. 复制一份 sourceArray，这一点很有必要，因为我们不能直接修改传入的数组的内容。和 Java 标准的 sort() 函数不一样，Java 标准的 sort() 函数是直接修改传入的数组，我们这里实现的排序算法是返回一份排序后的数组，不修改原始内容。
2. 插入函数中有两个循环。外层的循环依次处理数组中的每一个元素；也就是我们说的从堆的顶部取数据。变量 i 就是已排序数组的结束点的位置，也就是未排序数据的开始位置（|竖线的位置）。记住，在任意时刻，这数组的开始部分--从 index 0 到 index i --总是有序的。剩余部分，从 index i 到数组的最后一个元素是未排序的堆。
3. 内部循环检查处于位置 x 的元素。这就是处于堆顶部的数字，它有可能比它前面的元素都小。这一个循环向后逐一检查已经排序的数组；每当发现前面的元素比自己大，就交换两者的位置。当内部循环结束时，数组的开始部分就又变成有序的了，并且有序部分会增加一个元素。

注意： 外部循环是从 index 1 而不是 0 开始的。因为将堆中的第一个元素放入到已排序部分不会有任何改变，所以我们直接跳过他。

不使用交换函数

上面这个版本的插入排序可以正常的工作，但是我们可以通过移除对 swap 的调用，从而让它运行的更快一点。前面你已经看到我们通过交换数字的位置将下一个元素放入正确的位置：

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

我们可以不用和前面的元素交换位置，改而直接将这些元素向右移动一个位置，然后将新的数字放入正确的位置。

[ 3, 5, 8, 4 | 6 ]   记住 4
           *

[ 3, 5, 8, 8 | 6 ]   将 8 向右移动
        --->
        
[ 3, 5, 5, 8 | 6 ]   将 5 向右移动
     --->
     
[ 3, 4, 5, 8 | 6 ]   将 4 放入正确的位置
     *

来看看代码实现：

class InsertionSort {

    fun insertSort(sourceArray: IntArray): IntArray {
        val resultArray = sourceArray.clone()
        for (i in 1 until resultArray.size) {
            var y = i
            val insertValue = resultArray[y]
            while (y > 0 && insertValue < resultArray[y - 1]) {
                resultArray[y] = resultArray[y - 1]       //1
                y--
            }

            resultArray[y] = insertValue                  //2
        }

        return resultArray
    }

}

这里 //1 这一行代码将前一个元素向右移动一个位置。最循环的最后，y 就是新的数字在已排序部分的位置，所有在 //2 这一行将这个数字放入对应的位置。

通用的插入排序（泛型）

插入排序应该支持数字以外的其他类型排序。我们可以将参数的类型修改为泛型，并且使用外部传入的比较方法来实现大小比较。只需要在代码中修改两个地方就可以实现。

函数定义变成：

fun <T>insertSort(array: Array<T>, compare: (T, T) -> Boolean): Array<T> 

数组的类型是 T，也就是泛型的占位类型。现在 insertSort()方法可以接收任意类型的数组，不管它包含的是数字、字符串还是其他的数据。

新的参数 compare: (T, T) -> Boolean 是一个函数，它接收两个 T 对象并返回两个对象的大小比较结果，如果第一个参数小于第二个返回 true，反之则返回 false。

另一处修改就是内部循环，现在变成了：

while (y>0 && compare(insertValue, resultArray[y-1])){

我们不再使用 insertValue < resultArray[y - 1]比较大小，改为使用compare(insertValue, resultArray[y-1])函数，它们的作用是一样的，唯一不同的是我们现在可以比较任何类型的数据，不再局限于数字。

来看一看测试代码：

@Test
    fun insertSort() {
        val sorter = InsertionSort()
        val list: Array<Int> = arrayOf(10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26)
        val sortedList = sorter.insertSort(list) { x: Int, y: Int -> x < y }
        assertEquals(list.clone().apply { sort() }.joinToString(),
                sortedList.joinToString())

        val stringlist: Array<String> = arrayOf("b", "a", "d", "c", "e")
        val sortedStringList = sorter.insertSort(stringlist) { x: String, y: String -> x < y }
        assertEquals(stringlist.clone().apply { sort() }.joinToString(),
                sortedStringList.joinToString())
    }

从上面的测试代码可以看到，我们不仅可以对数字数组进行排序，同样可以对字符串数组排序。或者更复杂的对象进行排序：

val objList : Array<ComplextObject> = arrayOf(ComplextObject(3),ComplextObject(4),ComplextObject(0))
        sorter.insertSort(objList){obj1:ComplextObject, obj2:ComplextObject -> obj1.priority < obj2.priority}

上面的 lambda 表达式告诉 insertSort 方法根据 priority 属性对所有的对象进行排序。

插入排序是一种稳定的排序方法。所谓稳定的排序算法就是指：对于拥有相同排序键值的元素在排序后保持原来的相对位置不变。这一点对于一些简单的数据如数字或者字符串显得不是那么重要，但是对一些复杂的对象排序时非常重要。在上面的例子中，如果两个对象拥有相同的 priority，那么不管它们其他属性的值如何，这两个对象不会互相交换位置。

性能

插入排序对于有序队列会非常的快。这一点当然不用多说，但是这一点并非对所有的搜索算法都成立。在实际使用中，很多数据已经大部分排好序--如果没有完全排好序--插入排序会运行的非常好。

插入排序的最差复杂度和平均复杂度都是 O(n^2)。因为这个函数中有两重嵌套循环。其他的排序算法，比如快速排序和合并排序的复杂度是O(n log n)，这在数据量比较大的时候会获得更快的处理速度。

实际上插入排序在处理小的数组时会非常地快。有一些标准库的排序算法在待排序数据小于等于10时，会从快速排序切换到插入排序。

本文编译自：Swift 算法俱乐部 - 插入排序