日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：陳明勇 ? 更新時間： 2023-01-09 編程語言

插入排序

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

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

算法實現

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) 的查找時間復雜度，因此我認為沒有必要改造成二分查找。

原文鏈接：https://juejin.cn/post/7175178438095929404

欄目分類
最近更新