iOS 插入排序（Insertion Sort）

algo

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以形象地比喻成打扑克牌的时候整理牌的顺序的方法。

算法过程描述

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素作为新元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

动图演示

insertionSort.gif

复杂度

假设序列有n个元素，n>1，根据算法步骤，第1轮取第2个元素插入到已排序数列（1个元素）中，第2轮取第3个元素插入到已排序数列（有2个元素）中，… 第(n-1)轮取第n个元素插入到已排序数列（有(n-1)个元素）中。

函数表达式为：
f(n) = 1+2+…+(n-1)
f(n) = n*(n-1)/2
f(n) = (n²-n)/2

用大O表示法，忽略常量、低阶和常数系数。

时间复杂度为：O(n²)
空间复杂度为：并未开辟额外空间, 所以为O(1)
稳定性: 稳定

代码实现(Swift)

假设要对以下数组进行冒泡排序:

let numbers = [1, 4, 3, 2, 0, 5, 9, 7, 8, 6]

func insertionSort(numbers: [Int]) -> [Int] {
    
    var sortedNumbers = numbers
    
    // 默认第1个元素为有序
    for i in 1..<sortedNumbers.count {
        
        let temp = sortedNumbers[i]
    
        print("\n\(sortedNumbers) (\(i)th circle begin, num = \(temp)")
        
        for j in (0..<i).reversed() {
            
            if sortedNumbers[j] > temp {
                
                sortedNumbers.swapAt(j, j+1)
                
                print("swap at \(j) and \(j+1)")
            }
            else { // 0..<i 区间内为有序数组, 当没有出现更大的值时, 可以提前结束了
                break
            }
        }
    }
    
    return sortedNumbers
}

let sortedNumbers = insertionSort(numbers: numbers)
print("\n\(sortedNumbers) (insertion sort result)")

终端打印结果：

[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (1th circle begin, num = 4

[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (2th circle begin, num = 3
swap at 1 and 2

[1, 3, 4, 2, 0, 5, 6, 7, 8, 9] (3th circle begin, num = 2
swap at 2 and 3
swap at 1 and 2

[1, 2, 3, 4, 0, 5, 6, 7, 8, 9] (4th circle begin, num = 0
swap at 3 and 4
swap at 2 and 3
swap at 1 and 2
swap at 0 and 1

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (5th circle begin, num = 5

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (6th circle begin, num = 6

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (7th circle begin, num = 7

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (8th circle begin, num = 8

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (9th circle begin, num = 9

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (insertion sort result)

代码优化

插入排序也有一种优化算法，叫做拆半插入。个人感觉作用不是很大, 并且怎么优化时间复杂度都是O(n²)

感兴趣的可以参考这篇文章:拆半插入原理解析

回目录:常用的排序算法

结语

路漫漫其修远兮，吾将上下而求索~

作者简书

作者掘金

作者GitHub

.End