swift算法之排序：（三）插入排序

1、概述

插入排序是簡單直覺且穩定的排序算法。

插入排序的基本操作是将一個資料插入到已經排好序的有序資料中，進而得到一個新的、個數+1的有序資料，适用于少量資料的排序。

插入排序主要是将排序數組分成兩部分，第一部分是包含這個數組的左右元素，但最後一個元素除外（數組有多餘的空間才可插入），第二部分是需要插入的元素，在第一部分排序完成後，再将這個待插入放入元素插入到已排好序的第一部分中。

插入的過程其實是不斷交換和比較的過程。

2、算法原理

基本思想：每步将一個待排序的記錄，岸其關鍵碼值的大小插入前面已經排好序的數列的适當位置中，知道全部插入為止

步驟：

1）從第一個元素開始，該元素可以認為已經被排序

2）取出下一個元素，在已經排序的元素序列中從後往前掃描

3）如果該元素（已排序）大于新元素，将該元素移到下一個位置

4）重複3，直到找到已排序的元素小于或等于新元素的位置

5）将新元素插入到該位置

6）重複2）～5）

3、舉例

整理一個無序數組 [8, 3, 5, 4, 6]

1）取出第一個數字8，得到數組[8]，無序數組為[3, 5, 4, 6]

2）取出第二個數字3，插入新數組，3<8，得到[3, 8]，無序數組為[5, 4, 6]

3）取出第三個數字5，插入新數組，5<8且5>3，得到[3, 5 ,8]，無序數組為[4, 6]

4）取出第四個數字4，插入新數組，4<8、4<5、4>3，得到[3, 4, 5, 8]，無序數組為[6]

5）最後取出數字6，插入新數組，6>5、6<8，得到[3, 4, 5, 6, 8]，排序完成

4、算法實作

1）建立數組，符合條件的插入來實作插入排序

func insertSort(_ array : [Int])->[Int]{
        var list = array
        //建立一個空數組，符合條件的插入，沒插入的尾後添加
        var newList = [list[0]]
        //記錄循環的次數
        var count = 0
        for i in 1..<list.count {
//            var max : Int? = nil //從大到小排序
            var min : Int? = nil//從小到大排序
            count = i
            for j in 0..<newList.count {
//                if list[i] > newList[j] {
//                    max = i
                if list[i] < newList[j] {
                    min = i
                    newList.insert(list[i], at: j)
                    break
                }
                
            }
//            if max == nil {
//                newList.append(list[i])
//            }
            if min == nil {
                newList.append(list[i])
            }
        }
        print(newList)
        print("count: ",count)
         return newList
    }
           

2）通過交換數組資料實作插入排序

func insertSort1(_ array : [Int])->[Int]{
        var list = array
        //記錄循環次數
        var count = 0
        for i in 1..<list.count {
            //從i往前找，符合條件交換
            var y = i
            count = i
            //從大到小排序
//            while y>0 && list[y]>list[y-1]{
//                list.swapAt(y, y-1)
//                y -= 1
//            }
            //從小到大排序
            while y>0 && list[y]<list[y-1]{
                list.swapAt(y, y-1)
                y -= 1
            }
        }
        print(list)
        print("count: ",count)
        return list
    }
           

3）通過移動數組資料實作插入排序

func insertSort2(_ array : [Int])->[Int]{
        var list = array
        var count = 0
        for i in 1..<list.count {
            count = i
            //從i往前找，符合條件移動
            var y = i
            let tmp = list[y]
            //從大到小排序
//            while y>0 && tmp>list[y-1]{
//                list[y] = list[y-1]
//                y -= 1
//            }
            //從小到大排序
            while y>0 && tmp<list[y-1]{
                list[y] = list[y-1]
                y -= 1
            }
            list[y] = tmp
        }
        print(list)
        print("count: ",count)
        return list
    }
           

4）插入排序實作通用化

func insertSort3<T>(_ array : [T], _ isOrderedBefore:(T, T)->Bool)->[T]{
        var list = array
        var count = 0
        for i in 1..<list.count {
            count = i
            //從i往前找，符合條件移動
            var y = i
            let tmp = list[y]
            //從大到小排序
            //            while y>0 && tmp>list[y-1]{
            //                list[y] = list[y-1]
            //                y -= 1
            //            }
            //從小到大排序
            while y>0 && isOrderedBefore(tmp, list[y-1]){
                list[y] = list[y-1]
                y -= 1
            }
            list[y] = tmp
        }
        print(list)
        print("count: ",count)
        return list
    }
           

5）調用

let array3 = [8, 3, 5, 4, 6]
        SortSummary.insertSort(array3)
        SortSummary.insertSort1(array3)
        SortSummary.insertSort2(array3)
        SortSummary.insertSort3(array3, <)
        //insertSort3(array3){$0<$1}等同于insertSort3(array3, <)
        SortSummary.insertSort3(array3){$0<$1}
        SortSummary.insertSort3(array3, >)


運作結果：
1）建立數組
[3, 4, 5, 6, 8]
count:  4

2）交換
[3, 4, 5, 6, 8]
count:  4

3）移動
[3, 4, 5, 6, 8]
count:  4

4）通用方法
//從小到大排列
[3, 4, 5, 6, 8]
count:  4
[3, 4, 5, 6, 8]
count:  4
//從大到小排列
[8, 6, 5, 4, 3]
count:  4
           

5、時間複雜度

1）最好的情況下，完全沒有任何資料移動，即O(n)

2）最壞的情況下(平均性能表現)，比較的次數為(n+2)*(n+1)/2,移動的次數最大值(n+4)*(n-1)/2, 即O(n^2)

3）平均時間複雜度為 O(n^2)

github代碼

注：排序的具體實作代碼在 SortSummary.swift 檔案裡 調用是在 ViewController.swift