排序（Sort）是計算機程序設(shè)計中十分常見且重要的操作。是將一個數(shù)據(jù)元素的序列，重新排列成一個按關(guān)鍵字有序的序列。最近學(xué)習(xí)算法，從最基礎(chǔ)的排序開始，記錄一下。簡單溫習(xí)下最基礎(chǔ)的三類算法：選擇，冒泡，插入。

冒泡排序

冒泡排序（Bubble Sort）的基本思想是，對相鄰的元素進(jìn)行兩兩比較，順序相反則進(jìn)行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，最終達(dá)到完全有序

冒泡排序示意圖

在代碼實現(xiàn)中，為了避免不必要的比較，可以設(shè)置標(biāo)志位，如果某一趟執(zhí)行完畢，沒有做任何一次交換操作，則待排序列已經(jīng)有序，排序已經(jīng)完成。冒泡排序每一趟找到最大值，所以外層循環(huán)只需要到n-1即可（最后一個必然是最小的）。內(nèi)層循環(huán)每次比較都是除去 數(shù)組最右邊已經(jīng)有序的部分。

// 冒泡排序swift
public func bubbleSort(array: inout [Int]) {
    let count = array.count
    for i in 0..<count-1 {
    /*設(shè)定一個標(biāo)記，若為true，則表示此次循環(huán)沒有
    進(jìn)行交換，則待排序列已經(jīng)有序，排序已然完成。*/
        var flag = true
        for j in 0..<count-1-i {
            if array[j] > array[j+1] {
                swap(&array[j], &array[j+1])
                flag = false
            }
        }
        if flag {
            break
        }
    }
}

時間復(fù)雜度：如果初始序列就是有序的（最好情況），僅需n-1次比較就可完成。如果初始序列是反序的，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄來達(dá)到交換記錄位置。在這種情況下，比較次數(shù)為 n-1+n-2+...+1=n(n-1)/2，因此冒泡排序時間復(fù)雜度為$ O(n^2) $。

選擇排序

選擇排序（Selection Sort）基本思想是：每一趟在n-i+1(i=1,2,...,n-1)個記錄中選擇選取最小的記錄作為有序序列中第i個元素。

在代碼實現(xiàn)中，可以通過變量記錄每一趟的最小值，每一趟循環(huán)完畢之后，最后與位置i交換。代碼比較簡單明了，外層循環(huán)從0到n-1，內(nèi)層循環(huán)假設(shè)位置i為最小值，所以比較直接從i+1的位置開始。

// 選擇排序swift
public func selectionSort(array: inout [Int]) {
    let count = array.count
    for i in 0..<count-1 {
        // 選擇出最小的數(shù)
        var minIndex = i
        for j in i+1..<count {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }
        //進(jìn)行交換，如果minIndex發(fā)生變化，則進(jìn)行交換
        if i != minIndex {
            swap(&array[i], &array[minIndex])
        }
    }
}

時間復(fù)雜度：
選擇排序過程中，所需要進(jìn)行記錄移動的操作較少，但是，無論記錄初始化排列如何，需要進(jìn)行關(guān)鍵字的比較次數(shù)相同，均為n(n-1)/2，因此，選擇排序的時間復(fù)雜度為$ O(n^2) $

直接插入排序

直接插入排序基本思想是將一個記錄插入到已排好序的有序序列中，從而得到一個新的，記錄數(shù)增1的序列。

直接插入排序示意圖

算法代碼實現(xiàn)，從示意圖上，待插入元素不斷與前面元素進(jìn)行比較，交換位置，直到合適的位置。
其實每次交換是并不是必須的?？梢杂米兞縱alue 記錄將待插入元素，需要交換元素的時候，不交換元素，而是將更大的元素向右移動一個位置，最后value賦值到正確位置即可，減少交換次數(shù)，代碼如下。

// 插入排序swift
public func insertSort(array: inout [Int]) {
    let count = array.count
    for i in 1..<count {
        let value = array[i]
        var j = i
        while j > 0 && array[j-1] > value {
            array[j] = array[j-1]
            j -= 1
        }
        array[j] = value
    }
}

直接插入排序在最好情況下，需要比較n-1次，無需交換元素，時間復(fù)雜度為$ O(n) $;在最壞情況下，時間復(fù)雜度依然為$ O(n^2) $，但是總體來說插入排序比上面兩種排序更優(yōu)，主要原因大概有兩點，插入排序與哦

總結(jié)

上面三種最基本的算法（選擇，冒泡，插入），這三種排序算法的時間復(fù)雜度均為$ O(n^2) $。
其實排序算法已經(jīng)有像快速排序，堆排序這種時間復(fù)雜度為 $ n\log(n) $的排序，還有必要學(xué)習(xí)簡單排序算法么？當(dāng)然有必要，學(xué)習(xí)簡單排序的原因，簡單排序算法比較基礎(chǔ)，編碼上比較簡單，可以加深對排序算法的理解和了解。更重要的是高級復(fù)雜的排序也是從簡單排序中演化出來的，而且簡單排序在規(guī)模較小的時候，實際速度并不比快速排序慢。

后續(xù)會接著寫更復(fù)雜一些的排序算法如堆排序，快速排序，都會在github上更新，希望關(guān)注，有問題可以指出。

參考

• 數(shù)據(jù)結(jié)構(gòu)與算法分析
• 算法導(dǎo)論