使用插入排序算法对数组进行升序排序的 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() 来生成随机数，它用于设置种子值以生成伪随机数。我们需要通过实现插入排序算法来按升序对它们进行排序。上面的程序中的切片用作灵活且可扩展的数据结构来实现和管理数据集合。

结论

在上面的教程中，我们了解了如何在两个不同的示例中使用插入排序算法对数组进行升序排序，前提是第一个示例中的一个数组完全为正数，第二个示例中的数组包含负元素。