基於Go語言實現插入排序算法及優化

Posted on by

插入排序

插入排序是一種簡單的排序算法，以數組為例，我們可以把數組看成是多個數組組成。插入排序的基本思想是往前面已排好序的數組中插入一個元素，組成一個新的數組，此數組依然有序。光看文字可能不理解，讓我們看看圖示：

插入排序的時間復雜度為 O(N²)。

算法實現

import (
    "fmt"
)

func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原數組：", nums)
    fmt.Println("--------------------------------")
    InsertionSort(nums)
}

func InsertionSort(nums [4]int) {
    for i := 1; i < len(nums); i++ {
            for j := i; j > 0 && nums[j] < nums[j-1]; j-- {
                    nums[j], nums[j-1] = nums[j-1], nums[j]
            }
            fmt.Printf("第 %d 輪後：%v\n", i, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序後的數組：", nums)
}

執行結果：

原數組： [4 1 3 2]
——————————–
第 1 輪後：[1 4 3 2]
第 2 輪後：[1 3 4 2]
第 3 輪後：[1 2 3 4]
——————————–
排序後的數組： [1 2 3 4]

1.第一層循環的 i 變量，表示待排序的元素；

2.第二層循環：

j 變量的初值為 i 的值，由 j 變量往前去尋找待插入的位置；

  • 循環條件為 j > 0 && nums[j] < nums[j - 1]：
  • j > 0 → 尋找到左邊界則結束尋找；

nums[j] < nums[j - 1] → 左邊元素小於待排序的元素則結束尋找;

3.循環體為元素交換邏輯，隻要滿足循環條件，則不斷交換元素，直到交換到待插入的位置，才終止。

算法優化

上面的代碼，是通過不斷地交換元素，直到無法交換，才能將元素放置到待插入的位置，為瞭避免頻繁交換元素而導致效率低，將交換的邏輯變成把前面的數往後移，最後再將待排序的元素插入到合適的位置即可。

import (
    "fmt"
)

func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原數組：", nums)
    fmt.Println("--------------------------------")
    InsertionSort(nums)
}

func InsertionSort(nums [4]int) {
    for i := 1; i < len(nums); i++ {
        t := nums[i]
        j := i
        for ; j > 0 && t < nums[j-1]; j-- {
            nums[j] = nums[j-1]
        }
        nums[j] = t
        fmt.Printf("第 %d 輪後：%v\n", i, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序後的數組：", nums)
}

用變量 t 記錄待排序的元素，用 j 變量往前查找，隻要前面的數比 t 大，那麼就往後移，最後將 t 插入到合適的位置。

小結

本文首先對插入排序進行簡單地介紹，通過圖片來演示插入排序的過程，然後使用 Go 語言實現插入排序的算法。為減少算法中交換次數的邏輯，對算法進行優化，將交換的邏輯變成把前面的數往後移，最後將待排序的數插入到合適的位置即可。

除瞭這種優化方式，還有一種改造方式：普通的算法往左查找的方式是線性查找，由於元素是有序的，因此線性查找可以換成二分查找，但是經過二分找到待插入的位置之後，也得移動前面的元素，相比上面的優化方法，還多瞭 O(logn) 的查找時間復雜度，因此我認為沒有必要改造成二分查找。

到此這篇關於基於Go語言實現插入排序算法及優化的文章就介紹到這瞭,更多相關Go語言插入排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：