go 实现插入排序

曾经终败给现在 2021-07-24 13:58 453阅读 0赞

# 一 点睛 #

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

# 二 插入排序法思想 #

插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

# 三 图解 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 四 代码 #

package main
    
    import (
       "fmt"
    )
    
    func InsertSort(arr *[7]int) {
       for i := 1; i < len(arr); i++ {
          insertVal := arr[i]
          insertIndex := i - 1 // 下标
          // 从大到小
          for insertIndex >= 0 && arr[insertIndex] < insertVal {
             arr[insertIndex+1] = arr[insertIndex] // 数据后移
             insertIndex-- // 插入位置前移
          }
          // 插入
          if insertIndex+1 != i {
             arr[insertIndex+1] = insertVal
          }
          //fmt.Printf("第%d次插入后 %v\n",i, *arr)
       }
       /*
          // 完成第 2 次，给第 3 个元素找到合适的位置并插入
          insertVal = arr[2]
          insertIndex = 2 - 1 // 下标
          // 从大到小
          for insertIndex >= 0 && arr[insertIndex] < insertVal {
             arr[insertIndex + 1] = arr[insertIndex] // 数据后移
             insertIndex-- // 插入位置前移
          }
          // 插入
          if insertIndex + 1 != 2 {
             arr[insertIndex + 1] = insertVal
          }
          fmt.Println("第2次插入后", *arr)
    
          // 完成第 3 次，给第 4 个元素找到合适的位置并插入
          insertVal = arr[3]
          insertIndex = 3 - 1 // 下标
    
          // 从大到小
          for insertIndex >= 0 && arr[insertIndex] < insertVal {
             arr[insertIndex + 1] = arr[insertIndex] // 数据后移
             insertIndex-- // 插入位置前移
          }
          // 插入
          if insertIndex + 1 != 3 {
             arr[insertIndex + 1] = insertVal
          }
          fmt.Println("第3次插入后", *arr)
    
          //完成第 4 次，给第 5 个元素找到合适的位置并插入
          insertVal = arr[4]
          insertIndex = 4 - 1 // 下标
    
          // 从大到小
          for insertIndex >= 0 && arr[insertIndex] < insertVal {
             arr[insertIndex + 1] = arr[insertIndex] // 数据后移
             insertIndex-- // 插入位置前移
          }
          // 插入
          if insertIndex + 1 != 4 {
             arr[insertIndex + 1] = insertVal
          }
          fmt.Println("第4次插入后", *arr)*/
    }
    
    func main() {
       arr := [7]int{23, 0, 12, 56, 34, -1, 55}
       //var arr [80000]int
       //for i := 0; i < 80000; i++ {
       // arr[i] = rand.Intn(900000)
       //}
       //fmt.Println(arr)
       //start := time.Now().Unix()
       //fmt.Println("原始数组=", arr)
       InsertSort(&arr)
       //end := time.Now().Unix()
       //
       //fmt.Println("main 函数")
       //fmt.Printf("插入排序耗时%d秒", end-start)
       fmt.Println(arr)
    }

# 五 测试 #

[56 55 34 23 12 0 -1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/3df90fe998a84004968725f56cd07f15.png