Golang 使用插入排序对数组进行升序排序

插入排序被定义为一个就地算法，并声明为一个稳定的算法。使用交换元素的思想可以实现插入排序来对数组按升序或降序进行排序。例如，如果数组中只包含一个元素，则认为它已经排序。否则，我们认为列表的某个部分元素已经排序，而另一个部分未排序。根据这个假设，我们通过遍历未排序列表，依次选择一个元素。

语法

rand.Seed(value)

Rand.Seed() 函数用于生成随机数。它接受一个用户输入作为参数，该参数是生成随机数的上限。

func Now() Time

在time包中定义了 Now() 函数。这个函数生成当前的本地时间。要使用这个函数，我们必须先在我们的程序中导入time包。

func (t Time) UnixNano() int64

UnixNano()函数定义在time包中。此函数用于获取从协调世界时1970年1月1日起经过的秒数。它返回的最终结果为64位整数类型。

rand.Intn(n)

函数 Intn() 定义在math/rand包中。它用于在区间[0, n]中生成一个随机数，其中n是用户提供的数字。如果提供的数字小于0，该函数会抛出错误。

步骤步骤

步骤1 - 如果是第一个元素，则列表中的元素已经排序。

步骤2 - 如果步骤1返回false，即列表未排序，则选择下一个元素，即关键字。

步骤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]

问题解决方案

在上述程序中，我们将从用户那里读取一个元素数组，然后使用插入排序将数组按升序排序，然后将排序后的数组打印在输出屏幕上。

解释

在上面的示例中，我们声明了主要包。此主要包用于告诉编译器该包将进行编译并生成可执行文件。

我们还导入了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]