插入排序算法讲解及swift代码实现

插入排序算法解释和快速代码实现 从数组其他元素开始排序。如果取出的元素比本元素小，则放在本元素的左边；否则，它将被放置在右侧。一般来说，这看起来有点像在玩扑克时对你刚刚拿起的牌进行排序。

插入排序也是一个两级循环：

• 外层循环的边界是[1, array.count)，索引是i。
• 内循环以初始索引 j = i 开始，然后使用 while 循环。循环条件为 j>0 && Array[j] ，循环内部交换 j-1 和 j 的元素，使 j-1。很容易理解，如果当前元素比前一个元素小，则切换位置；否则执行下一个外循环。

我们来看看手写迭代的插入排序机制。使用的数组与上面的选择排序数组相同： [4, 1, 2, 5, 0]

i = 1 :

1. j = 1: array[1 ] [1, 4, 2, 5, 0]，j-1不符合内循环条件，退出内循环，i+1。 如果

i = 2:

1. j = 2, array[3] ⸸4, 5, 0] , j 移动到左，Array[2] > Array[1]，不满足内循环条件，退出内循环，i+1。如果

i = 3，：

1. j = 3，array[3] > array[2]，不满足内循环条件，退出内循环i+1。

如果

i = 4:

1. j = 4, array[4] ⸸ ,j-1。
2. j = 3，数组[3] [1, 2, 0, 4, 5]，j -1。
3. j = 2，数组[2] [1, 0, 2, 4, 5]，j -1。
4. j = 1，array[1] [0, 1, 2, 4, 5]，j -1 = 0，与内部不匹配层循环条件，退出内层循环，i+1 = 5，不符合外层循环条件，终止排序。

从上面的描述可以看出，相比选择排序，插入排序的内循环可以提前启动，条件是array[j] > = Array[ j - 1]，即只要当前索引为j的元素比前一个元素大，那么内循环就立即退出，不需要再次排序，因为算法把小的放到了从一开始就是第一个。 ，把大的放在后面。

代码实现

我们来看看如何通过代码来实现插入排序算法：

func insertionSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 1..<array.count {
        
        var j = i
        while j > 0 && array[j] < array[j - 1] {
             array.swapAt(j - 1, j)
            j -= 1
        }
    }
    return array
}
复制代码

从上面的代码中我们可以看到插入排序内循环的条件：❀j > 0 && array [j]