使用插入排序演算法對陣列進行升序排序的 Go 語言程式

---

插入排序被定義為一種原地演算法，並且被宣告為一種穩定演算法。透過交換元素來對陣列進行升序或降序排序的思想可以用來實現插入排序。例如，如果陣列中只有一項，則認為該陣列已排序。否則，我們認為元素列表的某一部分已排序，而另一部分未排序。根據此假設，我們遍歷未排序的列表，每次選擇一個元素。

語法

rand.Seed(value)

Rand.Seed() 函式用於生成隨機數。它以使用者輸入作為引數，該引數是生成隨機數的上限。

func Now() Time

Now() 函式定義在 time 包中。此函式生成當前本地時間。要使用此函式，我們必須首先在程式中匯入 time 包。

func (t Time) UnixNano() int64

UnixNano() 函式定義在 time 包中。此函式用於獲取自 1970 年 1 月 1 日以來的 UTC 時間的秒數。它返回的最終結果為 64 位整數型別。

rand.Intn(n)

Intn() 函式定義在 math/rand 包中。它用於在 [0, n] 區間內生成隨機數。其中 n 是使用者提供的數字。如果提供的數字小於 0，則該函式會丟擲錯誤。

演算法步驟

步驟 1 - 如果它是第一個元素，則列表中的元素已排序。

步驟 2 - 如果步驟 1 為假，即列表未排序，則選擇下一個元素，稱為鍵值。

步驟 3 - 將步驟 2 中的鍵值與已排序子列表中的所有元素進行比較。

步驟 4 - 將大於鍵值的已排序子列表中的元素進行移位。

步驟 5 - 將鍵值插入到已排序列表中的適當位置。

步驟 6 - 重複每個步驟，直到列表排序完成。

示例

使用插入排序演算法對整數陣列進行升序排序。

package main
import "fmt"
func main() {
   arr := [6]int{5, 7, 3, 4, 1, 2}
   var flag int = 0
   var item int = 0

   // printing the array
   fmt.Println("The array entered by the user is:\n", arr)

   //Insertion Sort to arrange elements in ascending order
   for i := 0; i < 6; i++ {
      item = arr[i]
      flag = 0
      for j := i - 1; j >= 0 && flag != 1; j-- {
         if item < arr[j] {
            arr[j+1] = arr[j]
            j = j - 1
            arr[j+1] = item
         } else {
            flag = 1
         }
      }
   }
   // printing new line
   fmt.Println()

   // printing the result
   fmt.Println("Array after sorting is: \n", arr)
}

輸出

The array entered by the user is:
[5 7 3 4 1 2]
Array after sorting is:
[2 4 2 5 2 7]

問題解決方案

在上面的程式中，我們將從使用者那裡讀取一個元素陣列，然後使用插入排序演算法對陣列進行升序排序，最後在輸出螢幕上列印排序後的陣列。

解釋

在上面的示例中，我們聲明瞭 main 包。此 main 包用於指示編譯器該包將進行編譯，然後生成可執行檔案。

我們還匯入了 fmt 包。fmt 代表格式化包。此包用於格式化基本字串和值。它將用於包含 fmt 包，這使我們能夠使用與 fmt 相關的函式。

示例

使用隨機值使用插入排序演算法對整數陣列進行升序排序。

package main
import (
   "fmt"
   "math/rand" // math/rand package provides pseudorandom number generation
   "time" // time package provides functionality for measuring and displaying time
)
func main() {
   
   // calling the generateSlice() function
   slice := generateSlice(20)
   fmt.Println("Unsorted Numbers are:\n", slice)
   insertionsort(slice)
   fmt.Println("Sorted Numbers are:\n", slice, "\n")
}

// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
   slice := make([]int, size, size)
   
   // generating a random number from the seconds passed from 1 january 1970 to current time.
   rand.Seed(time.Now().UnixNano())
   for i := 0; i < size; i++ {
      slice[i] = rand.Intn(100) - rand.Intn(100)
   }
   return slice
}
func insertionsort(items []int) {
   var n = len(items)
   for i := 1; i < n; i++ {
      j := i
      for j > 0 {
         if items[j-1] > items[j] {
            items[j-1], items[j] = items[j], items[j-1]
         }
         j = j - 1
      }
   }
}

輸出

Unsorted Number
[-28 -35 -26 -3 4 27 14 -30 26 50 -32 2 68 15 -7 10 -1 60 7 -62]
Sorted Number
[-62 -35 -32 -30 -28 -26 -7 -3 -1 2 4 7 10 14 15 26 27 50 60 68]

解釋

在上面的程式中，我們使用了 rand.Seed() 來生成隨機數，它用於設定種子值以生成偽隨機數。我們需要透過實現插入排序演算法來按升序對它們進行排序。上面的程式中的切片用作靈活且可擴充套件的資料結構來實現和管理資料集合。

結論

在上面的教程中，我們瞭解瞭如何在兩個不同的示例中使用插入排序演算法對陣列進行升序排序，前提是第一個示例中的一個數組完全為正數，第二個示例中的陣列包含負元素。