插入排序

参考链接

• 白话经典算法系列之二 直接插入排序的三种实现

基本思想

每次将一个待排序的元素，插入到前面已经排好序的子序列中，直到全部元素插入完成为止。

打过扑克牌的人都应该能够秒懂！！！

插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。

算法的实现

extension Array where Element: Comparable {
    mutating func insertSort() {
        /*
         1. 整个排序过程共进行n-1趟
         2. 每次取一个元素插入到前面排好序的数组中
         */
        for i in 1 ..< count {
            let insert = self[i]
            var j = i
            while j >= 1, insert < self[j - 1] {
                self[j] = self[j - 1]
                j -= 1
            }

            self[j] = insert
        }
    }
}

改进

将 array[j] 插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。

• 如果 array[j] 前一个数据 array[j-1] > array[j]，就交换 array[j] 和 array[j-1]，再 j--

• 直到 array[j-1] <= array[j]。这样也可以实现将一个新数据并入到有序区间。

extension Array where Element: Comparable {
    mutating func insertSort2() {
        /// 每次取一个元素插入
        for insert in 1 ..< count {
            var current = insert
            while current > 0 {
                let prev = current - 1
                /// 如果插入元素小于前一个元素就交换2者，直到找到合适插入位置
                if self[current] < self[prev] {
                    swapAt(current, prev)
                    current -= 1
                } else {
                    break
                }
            }
        }
    }
}