插入排序

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

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

算法實(shí)現(xiàn)

import (
    "fmt"
)

func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原數(shù)組：", 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("排序后的數(shù)組：", nums)
}

執(zhí)行結(jié)果：

原數(shù)組： [4 1 3 2]
--------------------------------
第 1 輪后：[1 4 3 2]
第 2 輪后：[1 3 4 2]
第 3 輪后：[1 2 3 4]
--------------------------------
排序后的數(shù)組： [1 2 3 4]

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

2.第二層循環(huán)：

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

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

nums[j] < nums[j - 1] → 左邊元素小于待排序的元素則結(jié)束尋找;

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

算法優(yōu)化

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

import (
    "fmt"
)

func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原數(shù)組：", 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("排序后的數(shù)組：", nums)
}

用變量 t 記錄待排序的元素，用 j 變量往前查找，只要前面的數(shù)比 t 大，那么就往后移，最后將 t 插入到合適的位置。

小結(jié)

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

除了這種優(yōu)化方式，還有一種改造方式：普通的算法往左查找的方式是線性查找，由于元素是有序的，因此線性查找可以換成二分查找，但是經(jīng)過二分找到待插入的位置之后，也得移動(dòng)前面的元素，相比上面的優(yōu)化方法，還多了 O(logn) 的查找時(shí)間復(fù)雜度，因此我認(rèn)為沒有必要改造成二分查找。

到此這篇關(guān)于基于Go語言實(shí)現(xiàn)插入排序算法及優(yōu)化的文章就介紹到這了,更多相關(guān)Go語言插入排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論