排序算法——插入排序

前言

插入排序，以从小到大排序为例。

原理

以从小到大排序为例。
创建一个新数组标记为已排序的数组。将待排序的第一位加入到已排序数组中，然后待排序数组从第二位遍历。将待排序的数字与已排序数组中比较（从后向前），插入到相应位置。

算法实现

Swift 4

func insertionSort(array: [Int]) -> [Int]{
    var sortedArray = [Int]()
    //将第一个加入已排序
    sortedArray.append(array[0])
    
    if array.count > 1 {
        for index in 1...array.count - 1 {
            let number = array[index]
            
            //反向遍历找到要插入到已排序的数组中下标
            for (sortIndex, sortNumber) in sortedArray.enumerated().reversed() {
                if sortNumber <= number {
                    sortedArray.insert(number, at: sortIndex + 1)
                    break
                }
            }
        }
    }
    
    for number in sortedArray {
        print(number)
    }
    return sortedArray
}

func insertionSort2(array: inout [Int]) -> [Int] {
    let count = array.count
    
    if count > 1 {
        for i in 1..<count {
            let temp = array[i]
            var index = i
            while index >= 1 && array[index-1] > temp {
                array[index] = array[index-1]
                index -= 1
            }
            array[index] = temp
        }
    }
    print(array)
    return array
}

动画展示

来自：visualgo