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

使用插入式排序法对数组进行升序排序的Golang程序

插入排序被定义为一种就地算法，它被宣布为一种稳定的算法。通过交换一个元素对数组进行升序或降序排序的想法可以用来实现插入式排序。例如，如果数组中只包含列表中的一个项目，那么它被认为是排序的。否则，我们认为列表中的某一部分元素是被排序的，而其他元素是未排序的。根据这个假设，我们遍历未排序的列表，每次挑选一个元素。

语法

rand.Seed(value)

Rand.Seed() 函数是用来生成随机数的。它需要一个用户输入作为参数，这是生成随机数的上限。

func Now() Time

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

func (t Time) UnixNano() int64

UnixNano()函数被定义在时间包中。这个函数用来获取从1970年1月1日开始的秒数，单位是UTC。它返回的最终结果是64位的整数类型。

rand.Intn(n)

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

算法步骤

第1步 – 如果它是第一个元素，那么列表中的元素就已经被排序了。

第2步 – 如果第1步是假的，即列表没有被排序，那么就选取下一个元素，称为key

第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()来生成随机数 它是用来设置一个种子值来生成伪随机数。我们需要通过实施插入式排序将它们按升序排序。上述程序中的Slice是作为一种灵活和可扩展的数据结构来实现和管理数据集合的。

结论

在上面的教程中，我们已经了解了如何在2个不同的例子中使用插入排序对数组进行升序排序，在第一个例子中，一个数组完全是正数，而第二个数组中的元素是负数。