本文只是自己的筆記鞋仍，并不具備過多的指導(dǎo)意義常摧。

代碼的初衷是便于理解，網(wǎng)上大神優(yōu)化過的代碼很多威创，也不建議在項(xiàng)目中copy本文代碼落午。

目錄

• 時(shí)間復(fù)雜度
  • 常數(shù)時(shí)間的操作
  • 時(shí)間復(fù)雜度的計(jì)算
  • 常數(shù)操作表達(dá)式類型的時(shí)間復(fù)雜度
  • 時(shí)間復(fù)雜度相同的比對(duì)
• 冒泡排序
  • 改進(jìn)版的冒泡排序
• 選擇排序
  • 二元選擇排序
• 插入排序
• 時(shí)間復(fù)雜度的最差情況，最好情況肚豺，平均情況
• *對(duì)數(shù)器

時(shí)間復(fù)雜度

衡量代碼的好壞溃斋，包括兩個(gè)非常重要的指標(biāo)：運(yùn)行時(shí)間與占用空間。

而時(shí)間復(fù)雜度正代表前者吸申，后者由空間復(fù)雜度(_{即算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度})表示梗劫。

• 常數(shù)時(shí)間的操作

一個(gè)操作如果和數(shù)據(jù)量沒有關(guān)系，每次都是固定時(shí)間內(nèi)完成的操作截碴，叫做常數(shù)操作在跳。
比如數(shù)組下標(biāo)的尋址，一對(duì)下標(biāo)交換隐岛。

• 常數(shù)操作數(shù)量

單次常數(shù)時(shí)間的操作，寫作做O(1)瓷翻。讀作big O 1 聚凹。

• 時(shí)間復(fù)雜度的計(jì)算

法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示齐帚。
若有一個(gè)函數(shù)妒牙，f(N)。當(dāng)N趨近于無窮大時(shí)对妄，使得T(n)/f(n)趨近于一個(gè)不為0的常數(shù)湘今。
則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))剪菱，稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度摩瞎，簡(jiǎn)稱時(shí)間復(fù)雜度拴签。

• 線性的時(shí)間復(fù)雜度

比如一個(gè)算法共需要執(zhí)行N次循環(huán)，每次循環(huán)內(nèi)部都是常數(shù)操作O(1)

for i in 1..<N+1 {
    //常數(shù)操作
    let firstItem = arr[i-1]
    let secondItem = arr[i]
    if firstItem > secondItem {
        arr.swapAt(i-1, i)
    }
}

的T(N)=F(N)=N旗们，時(shí)間復(fù)雜度為O(F(N))=O(N)蚓哩。

• 常數(shù)操作表達(dá)式類型的時(shí)間復(fù)雜度

對(duì)于T(N)為達(dá)式類型的時(shí)間復(fù)雜度，F(xiàn)(N)簡(jiǎn)而言之就是要簡(jiǎn)化成當(dāng)N趨近無窮大時(shí),表達(dá)式中對(duì)其影響最大的一項(xiàng)的表達(dá)式上渴。

具體來說岸梨。在常數(shù)操作數(shù)量的表達(dá)式中， 只要高階項(xiàng)稠氮，不要低階項(xiàng)曹阔，也不要高階項(xiàng)的系數(shù)，剩下的部分 如果記為f(N)隔披，那么時(shí)間復(fù)雜度為O(f(N))赃份。

借用百度百科上的例子：

for(i=1; i<=n; ++i)
{
    c[i];//該步驟屬于基本操作執(zhí)行次數(shù)：n
    for(j=1; j<=n; ++j)
    {
        c[i][j] = 0;//該步驟屬于基本操作執(zhí)行次數(shù)：n的平方次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//該步驟屬于基本操作執(zhí)行次數(shù)：n的三次方次
    }
}

T(N) = A×N3+B×N2+C×N。當(dāng)N趨近于無窮大時(shí)锹锰，三次方的影響遠(yuǎn)大于二次方以及一次方芥炭。當(dāng)然也大于常數(shù)項(xiàng)A的影響。
所以表達(dá)式f(N)=N3恃慧。
時(shí)間復(fù)雜度為O(N)=O(f(N))=O(N3)

領(lǐng)附一張圖方便理解高階項(xiàng)在基數(shù)變大時(shí)的變化：

• 時(shí)間復(fù)雜度相同的比對(duì)

評(píng)價(jià)一個(gè)算法流程的好壞园蝠，先看時(shí)間復(fù)雜度的指標(biāo)，然后再分
析不同數(shù)據(jù)樣本下的實(shí)際運(yùn)行時(shí)間痢士，也就是常數(shù)項(xiàng)時(shí)間彪薛。

冒泡排序

在冒泡排序過程中會(huì)將數(shù)組分成兩部分，前半部分是無序的數(shù)列怠蹂，后半部分為有序的數(shù)列善延。無序數(shù)列中不斷的將其中最大的值往有序序列中冒泡，泡冒完后城侧，我們的序列就創(chuàng)建好了易遣。

具體操作上，如果相鄰的兩個(gè)數(shù)字前者較大嫌佑，則將二者交換钙姊，到達(dá)無序數(shù)組邊界則停止蜀踏。

func bubbleSort(arr: inout [Int]) {
    if arr.count < 2 {
        return
    }
    
    for i in 0..<arr.count {
        for j in 0..<arr.count - (i+1) {
            if arr[j] > arr[j+1] {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
}

時(shí)間復(fù)雜度O(N2)攻锰，額外空間復(fù)雜度O(1)饲趋。

時(shí)間復(fù)雜度的來源f(N) = N +( N -1) + (N-2) + ...+ 2 + 1 為一個(gè)等差數(shù)列。前N項(xiàng)和的通用公式為:N*(N-1)/2化簡(jiǎn)后f(N)=N2炮温。

• 改進(jìn)版的冒泡排序

經(jīng)典的冒泡排序火脉，無論數(shù)組是否已經(jīng)有序。都會(huì)一次次的遍歷，從這一點(diǎn)上我們可以進(jìn)行改進(jìn)

func bubbleSort2(arr: inout [Int]) {
    if arr.count < 2 {
        return
    }
    var swapped = false //記錄是否有交換動(dòng)作的變量
    for i in 0..<arr.count {
        swapped = false
        for j in 0..<arr.count - (i+1) {
            if arr[j] > arr[j+1] {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                swapped = true //有交換動(dòng)作則記錄
            }
        }
        if swapped == false {
            break //沒有交換動(dòng)作倦挂，說明已經(jīng)有序
        }
    }
}

極端情況下(對(duì)于一個(gè)已經(jīng)有序的數(shù)組)畸颅，算法完成第一次外層循環(huán)后就會(huì)返回。
實(shí)際上只發(fā)生了 N - 1次比較妒峦，所以最好的情況下重斑，該算法復(fù)雜度是O(N)。

選擇排序

基本思想與冒泡排序相同肯骇。前半部分為序的數(shù)列窥浪，只不過后半部分是無序的數(shù)列。無序數(shù)列中不斷的將其中最大的值往有序序列中冒泡笛丙，泡冒完后漾脂，我們的序列就創(chuàng)建好了。

具體操作上胚鸯，每次遍歷記錄無序序列中最小值的位置骨稿，并在結(jié)束時(shí)與無序序列的首位置交換，使其變成有序序列的最后一位姜钳。

func selectionSort(arr : inout [Int]) {
    if arr.count<2 {
        return
    }
    var minIndex :Int
    for i in 0..<arr.count {
        minIndex = i
        for j in i+1..<arr.count { //循環(huán)從i+1開始坦冠，也就是無序數(shù)組的第二位開始
            minIndex = arr[j]<arr[minIndex] ? j:minIndex //比對(duì)當(dāng)前位置與記錄位置的值，記錄其中最小的哥桥。
        }
        arr.swapAt(i, minIndex) //將無序數(shù)組的第一位與最小一位交換
    }
}

• 二元選擇排序

選擇排序本身沒有什么可改進(jìn)的辙浑，但是我們可以左右開弓。

將序列分成三個(gè)部分拟糕，前段有序部分判呕，中段無序部分，后端有序部分送滞。
每次循環(huán)侠草，將最大值與最小值分別置入前后兩個(gè)有序序列。

func selectionSort2(arr : inout [Int]) {
    if arr.count<2 {
        return
    }
    var minIndex :Int
    var maxIndex :Int
    for i in 0..<arr.count {
        minIndex = i
        maxIndex = i
        if i+1 >= arr.count - i {
            return // 由于這一步的存在犁嗅，實(shí)際上會(huì)在i=arr.count/2處結(jié)束循環(huán)
        }
        for j in i+1..<arr.count - i { //循環(huán)從i+1開始边涕，也就是無序數(shù)組的第二位開始。并且在后端有序序列的前一位停止
            minIndex = arr[j]<arr[minIndex] ? j:minIndex //比對(duì)當(dāng)前位置與記錄位置的值褂微，記錄其中最小的功蜓。
            maxIndex = arr[j]>arr[maxIndex] ? j:maxIndex //比對(duì)當(dāng)前位置與記錄位置的值，記錄其中最大的蕊梧。
        }

        if maxIndex == i && minIndex == arr.count - (i+1) {
            //如果最大值與最小值恰好處于邊界，直接交換會(huì)導(dǎo)致亂序腮介。需要手動(dòng)賦值
            let maxValue = arr[maxIndex];
            let minValue = arr[minIndex];
            let maxToValue = arr[arr.count - (i+1)]
            let minToValue = arr[i]
            
            arr[maxIndex] = maxToValue
            arr[arr.count - (i+1)] = maxValue
            arr[minIndex] = minToValue
            arr[i] = minValue
            
        }else if maxIndex == i{
            //如果最大值位置處于最小值將要交換的位置肥矢，先交換最大值
            arr.swapAt(arr.count - (i+1) , maxIndex) //將無序數(shù)組的最后一位與最大一位交換
            arr.swapAt(i, minIndex) //將無序數(shù)組的第一位與最小一位交換
        }else  {
            arr.swapAt(i, minIndex) //將無序數(shù)組的第一位與最小一位交換
            arr.swapAt(arr.count - (i+1) , maxIndex) //將無序數(shù)組的最后一位與最大一位交換
        }
    }
}

這樣雖然復(fù)雜度還是O(N2)，但實(shí)際上的表達(dá)式系數(shù)比經(jīng)典選擇排序不止縮小了1/2。

插入排序

基本思想也是前半部分為序的數(shù)列甘改，后半部分是無序的數(shù)列旅东。無序數(shù)列不斷將其首位元素推給有序數(shù)列，有序數(shù)列將其插入適當(dāng)?shù)奈恢谩?/p>

具體操作上十艾，會(huì)從有序數(shù)列的尾部依次向前比較抵代，若前位大于后位則進(jìn)行交換。

func insertionSort(arr : inout [Int]) {
    if arr.count<2 {
        return
    }
    for i in 1..<arr.count { //無序數(shù)組從i=1到末尾
        for j in (0...i-1).reversed() {  //從 i-1 位置到 0位置的有序數(shù)組內(nèi)進(jìn)行循環(huán)
            if arr[j+1] > arr[j] {  //j+1當(dāng)?shù)谝淮螆?zhí)行的時(shí)候忘嫉，正位于無序數(shù)組的首位置
                break //如果后位置大于前位置荤牍，說明已經(jīng)有序。退出當(dāng)前循環(huán)
            }
            arr.swapAt(j, j+1)//否則交換
        }
    }
}

改進(jìn)的話庆冕，或許可以試試用二分法確定具體位置然后進(jìn)行整體后移并插入康吵。

時(shí)間復(fù)雜度的最差情況，最好情況访递，平均情況

對(duì)于插入排序這種有明確終止條件的排序晦嵌，實(shí)際的時(shí)間復(fù)雜度與數(shù)據(jù)的實(shí)際狀況有關(guān)。
最好情況是最開始便有序拷姿，我們只需要執(zhí)行一次大循環(huán)惭载，復(fù)雜度為O(N)。
最差情況是將整個(gè)數(shù)組倒序排列一次响巢，復(fù)雜度為O(N2)描滔。
平均情況是指在大數(shù)狀況下的平均期望復(fù)雜度。

在數(shù)據(jù)的實(shí)際狀況對(duì)算法流程存在影響時(shí)抵乓，使用最差情況作為時(shí)間復(fù)雜度伴挚。

不過，我們可以利用主動(dòng)打亂數(shù)據(jù)狀況影響的方式灾炭。將復(fù)雜度易數(shù)學(xué)期望的方式表達(dá)(參考隨機(jī)快排)茎芋。

對(duì)數(shù)器

對(duì)數(shù)器是用來測(cè)試代碼正確性的，我們?cè)谡也坏胶线m的oj系統(tǒng)測(cè)試自己的代碼時(shí)蜈出，可以自己寫一個(gè)對(duì)數(shù)器對(duì)代碼進(jìn)行測(cè)試田弥。

• 設(shè)計(jì)對(duì)數(shù)器的一般步驟為：

1.有一個(gè)你要測(cè)的方法a； 自己寫的方法
2.實(shí)現(xiàn)一個(gè)絕對(duì)正確即使復(fù)雜度不好的方法b铡原； 系統(tǒng)自帶方法即可
3.實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器偷厦；
4.實(shí)現(xiàn)比對(duì)的方法； 比對(duì)兩個(gè)結(jié)果最后是否一致
5.把方法a和方法b比對(duì)很多次來驗(yàn)證方法a是否正確
6.如果有一個(gè)樣本使得比對(duì)出錯(cuò)燕刻，打印樣本分析是哪個(gè)方法出錯(cuò)
7.當(dāng)樣本數(shù)量很多時(shí)比對(duì)測(cè)試依然正確只泼，可以確定方法a已經(jīng)正確

• 實(shí)現(xiàn)對(duì)數(shù)器

其中1，2卵洗，4已經(jīng)說了请唱。6弥咪，7也沒啥好說的。

3.實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器

/// 隨機(jī)數(shù)組生成器
///
/// - Parameters:
///   - size: 最大長(zhǎng)度
///   - value: 最大值
/// - Returns: 隨機(jī)數(shù)組
func generateRandomArray(size : Int ,value : Int) -> [Int] {
    var arr :[Int]
    arr = Array.init()
 
    for i in 0..<Int(arc4random() % 10) * size / 10  {
        let item = Int(arc4random() % 10)*value/10
        arr.append(item)
    }
    print(arr)
    return arr
}

• 把方法a和方法b比對(duì)很多次來驗(yàn)證方法a是否正確

var checkOK = true
for i in 0..<10000 {
    var arr1 = generateRandomArray(size: 5, value: 20)
    var arr2 = arr1 //數(shù)組在swift里屬于值類型十绑，賦值動(dòng)作會(huì)自動(dòng)copy
    let originalArr = arr1
    arr1.sort()
    heapSort(arr: &arr2)
    
    if arr1 != arr2 {
        checkOK = false
        print(originalArr)
        print(arr2)
        break
    }
}

print(checkOK ? "比對(duì)成功":"比對(duì)失敗")


//打印
[0, 6, 2, 12, 18]
[0, 6, 12, 2, 18]
比對(duì)失敗

錯(cuò)誤的原始數(shù)據(jù)已經(jīng)打印出來了聚至，你就可以隨意重現(xiàn)這個(gè)數(shù)據(jù)進(jìn)行調(diào)試了。

var arr = [0, 6, 12, 2, 18];
print(arr)
heapSort(arr: &arr)
print(arr)

參考資料

左神牛課網(wǎng)算法課
時(shí)間復(fù)雜度和空間復(fù)雜度的簡(jiǎn)單講解
選擇排序及改進(jìn)方法
十大經(jīng)典排序算法（動(dòng)圖演示）