Go語言數據結構之插入排序示例詳解

Posted on by

插入排序

插入排序，英文名（insertion sort）是一種簡單且有效的比較排序算法。

思想： 在每次迭代過程中算法隨機地從輸入序列中移除一個元素，並將改元素插入待排序序列的正確位置。重復該過程，直到所有輸入元素都被選擇一次，排序結束。

插入排序有點像小時候我們抓撲克牌的方式，如果抓起一張牌，我們放在手裡；抓起第二張的時候，會跟手裡的第一張牌進行比較，比手裡的第一張牌小放在左邊，否則，放在右邊。

因此，對所有的牌重復這樣的操作，所以每一次都是插入最正確的排序順序，直到牌抓完為止。

動畫演示

假設我們需要從小到大進行排序，動畫演示如下：

Go 代碼實現

package main
import "fmt"
func main() {
    arrays := []int{6, 2, 5, 8, 9, 3, 1}
    length := len(arrays)
    insertionSort(arrays, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d ", arrays[i])
    }
}
func insertionSort(unsorted []int, length int) {
    for i := 0; i < length; i++ {
        var insertElement = unsorted[i]
        var insertPosition = i
        for j := insertPosition - 1; j >= 0; j-- {
            if insertElement < unsorted[j] {
                unsorted[j+1] = unsorted[j]
                insertPosition--
            }
        }
        unsorted[insertPosition] = insertElement
    }
}

運行結果：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 數據結構\main.go"
1 2 3 5 6 8 9

總結

插入排序實現簡單，理解也較容易，數據量較少時效率高，算法的實際運行效率優於選擇排序和冒泡排序。

空間復雜度： 空間復雜度為 O(1)，即不輸入借助其他的輔助空間。

穩定性： 插入排序是穩定的排序算法，在鍵值相同時它能夠保持輸入數據的原有次序。

以上就是Go語言數據結構之插入排序示例詳解的詳細內容，更多關於Go 數據結構插入排序的資料請關註WalkonNet其它相關文章！

推薦閱讀：