冒泡、選擇、插入排序

三個時間復雜度為 O(n^2)的排序演算法

排序有很多種，有些演算法連名字都沒聽過，經過這段時間的刷題，我在這里總結一下幾個常見的排序，我們都知道，演算法是要考慮時間復雜度和空間復雜度的，所以我把演算法分了三類，分別是時間復雜度是 O(n^2)、O(nlogn)、O(n)，注意這里的時間復雜度是指平均時間復雜度，關于最壞情況下的時間復雜度和最好情況下的時間復雜度在下面討論，

對于排序演算法，我們需要了解幾個問題，演算法的時間復雜度是多少？是否是原地排序演算法？演算法是否穩定？

時間復雜度我個人感覺可以理解為代碼需要執行的次數，次數越多，所花費的時間就越長，當然是要在同等的資料量下比較，而原地排序的概念，可以扯到空間復雜度上面，原地排序，顧名思義就是直接在原陣列進行排序操作，不需要申請額外的記憶體空間，空間復雜度為 O(1)，最后是演算法是否穩定，何為穩定，當一個陣列中有兩個相等的數的時候，若排序之后，兩個相等的數的順序不會發生改變，這就是一個穩定的演算法，反之就是不穩當的演算法，

冒泡排序

顧名思義，就是要把待排序的元素一點點的往上替換，就好像氣泡從水里浮起來一樣，那它的具體實作程序呢？我們想象一組等待排序的元素，比如 2、5、1、7、0 這五個數字，如果我們要把它從小到大排序怎么辦，

按照冒泡的演算法，我們先把第一個和第二個兩個相鄰的數字，比較它們的大小，如果 2 比 5 大，就把 2 和 5 的位置互換，當然 2 肯定是比 5 小的，所以第一步不交換，第二步比較 5 和 1，這時 5 比 1 要大，所以把 5 和 1 的位置互換，重復這個操作，當第一次冒泡完成的時候，7 就已經排到了最后面，每次冒泡可以使得一個數字移動到它應該處于的位置上，重復 n 次就可以對 n 個資料完成排序，因此冒泡的時間復雜度是 O(n^2)，下面是演示

來看一下代碼實作,我這里使用的是 go 語言，但是原理都是一樣的,是不是很簡單，

package main
import "fmt"
func main(){
    a :=[]int{1,2,5,8,3,}
    bubbleSort(a)
    fmt.Println(a)
}
func bubbleSort(array []int) {//這里是實作冒泡排序的函式
    n := len(array)
    for i := 0; i < n; i++{
        for j := 1; j < n; j++{
            if array[j] < array[j-1] {
                temp := array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            }
        }
    }
}

當然，我們可以對冒泡排序做出一些優化，比如說當某一冒泡的時候沒有元素移動，這時候就可以停止了，因為沒有元素移動，說明已經是有序了，

可以看到，在代碼中只申請了一個臨時變數，交換程序都是直接在原陣列操作，所以冒泡排序是一個原地排序演算法，同時如果兩個數相等的時候，是可以不交換位置的，因此是一個穩定的演算法，

插入排序

上面的冒泡排序是對一個靜態的陣列排序，如果我們對一個已經有序的陣列插入一個值，怎么能保持它還是有序的呢？這就要用到插入排序了，

插入排序的思想就是把待排序的元素分為已排序部分和未排序部分，每一次從未排序部分中取出一個值，插入到已排序部分中，最后未排序部分為空時，就完成了對元素的排序，看動圖就容易理解了

代碼實作

package main
import "fmt"
func main(){
    a :=[]int{7,2,9,0,3,}
    insertionSort(a)
    fmt.Println(a)
}
func insertionSort(arr []int) []int {
        for i := range arr {
                preIndex := i - 1
                current := arr[i]
                for preIndex >= 0 && arr[preIndex] > current {
                        arr[preIndex+1] = arr[preIndex]
                        preIndex--
                }
                arr[preIndex+1] = current
        }
        return arr
}

關于插入排序的時間復雜度，在最好情況下，向一個有序的陣列中插入一個值，只需要遍歷一次，所以時間復雜度是 O(n)，在最壞情況下，陣列是倒序的，每次插入都相當于在陣列的第一個位置插入，所以時間復雜度是 O(n^2)，那么平均時間復雜度呢？我們知道在一個陣列中插入一個值的時間復雜度是 O(n)，那么插入 n 個資料就是 O(n^2)，

插入排序如同冒牌排序，也是一個原地排序演算法，同樣的可以不交換相等的數，因此也是一個穩定的演算法，

選擇排序

選擇排序和插入排序類似，也是需要先劃分出已排序部分和未排序部分，不過選擇排序是每次從未排序部分中選擇出最大或者最小的元素，然后插入到前面的已排序部分中，

在最好情況下，從第一個資料開始，每個都需要對陣列進行遍歷，即使我們知道這個陣列已經是有序的，但是按照演算法還是要逐個掃描，每向已排序部分插入一個值都要遍歷一次，因此時間復雜度是 O(n^2)，同樣的，不管是最壞情況，還是平均時間復雜度，都是 o(n^2)，

代碼

package main
import "fmt"
func main(){
    a :=[]int{7,2,9,0,3,}
    selectionSort(a)
    fmt.Println(a)
}
func selectionSort(array []int)[]int {
    length := len(array)
    if length < 2 {return array}
    for i := 0; i < length; i++ {
        for j := i; j < length; j++ {
            if array[j] < array[i] {
                temp := array[j]
                array[j] = array[i]
                array[i] = temp
            }
        }
    }
    return array
}

選擇排序是原地排序演算法嗎？當然是，和上面一樣，同樣是 o(1) 的空間復雜度，那選擇排序是一個穩定的演算法嗎？這就不是了，它每次把最小的交換到前面去，那么被交換到后面的數字可能和中間有的數字是相等的，這時候它們的順序就發生了改變，比如 3,4,6,3,2 這五個數字，第一輪會把第一個 3 和最后的 2 交換位置，這時兩個 3 的順序就發生改變了，所以是不穩定的演算法，

插入排序和冒泡排序相比較呢？插入排序又要比冒泡排序更好一點，同樣都是 O(n^2) 的時間復雜度和 O(1) 的空間復雜度，插入排序中賦值操作比冒泡中要少，資料少的時候差距不大，當資料量大的時候，多出來的這兩步賦值操作消耗的時間就很明顯了，

公眾號：沒有夢想的阿巧 后臺回復 "群聊"，一起學習，一起進步

標籤：其他

上一篇：鏈表深拷貝

下一篇：TCP 三次握手與四次揮手