go完成选择排序插入排序快速排序的性能测试

末蓝、 2021-07-25 00:58 410阅读 0赞

# 一 选择排序 #

## 1 代码 ##

package main
    
    import (
       "fmt"
       "math/rand"
       "time"
    )
    
    // 完成选择排序，从大到小
    func SelectSort(arr *[80000]int) {
       for j := 0; j < len(arr)-1; j++ {
          max := arr[j]
          maxIndex := j
          // 3 从 j+1 开始遍历，到 [len(arr) -1] 结束，和 max 进行比较
          for i := j + 1; i < len(arr); i++ {
             if max < arr[i] { // 找到真正的最大值
                max = arr[i]
                maxIndex = i
             }
          }
          // 交换
          if maxIndex != j {
             arr[j], arr[maxIndex] = arr[maxIndex], arr[j]
          }
          //fmt.Printf("第%d次 %v\n  ", j+1 ,*arr)
       }
    }
    
    func main() {
       var arr [80000]int
       for i := 0; i < 80000; i++ {
          arr[i] = rand.Intn(900000)
       }
       start := time.Now().Unix()
       SelectSort(&arr)
       end := time.Now().Unix()
       fmt.Printf("选择排序耗时=%d秒", end-start)
    }

## 2 测试 ##

> 选择排序耗时=4秒

# 二 插入排序 #

## 1 代码 ##

package main
    
    import (
       "fmt"
       "math/rand"
       "time"
    )
    
    func InsertSort(arr *[80000]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)
       }
    }
    
    
    func main() {
       var arr [80000]int
       for i := 0; i < 80000; i++ {
          arr[i] = rand.Intn(900000)
       }
       start := time.Now().Unix()
       InsertSort(&arr)
       end := time.Now().Unix()
       fmt.Printf("插入排序耗时%d秒", end-start)
    }

## 2 测试 ##

> 插入排序耗时1秒

# 三 快速排序 #

## 1 代码 ##

package main
    
    import (
       "fmt"
       "math/rand"
       "time"
    )
    
    // 快速排序
    // 说明
    // 1 left 表示数组左边的下标
    // 2 right 表示数组右边的下标
    // 3 array 表示要排序的数组
    func QuickSort(left int, right int, array *[24000000]int) {
       l := left
       r := right
       // pivot 是中轴， 支点
       pivot := array[(left+right)/2]
       temp := 0
       // for 循环的目标是将比 pivot 小的数放到左边，比 pivot 大的数放到右边
       for l < r {
          // 从 pivot 的左边找到大于等于pivot的值
          for array[l] < pivot {
             l++
          }
          // 从 pivot 的右边边找到小于等于pivot的值
          for array[r] > pivot {
             r--
          }
          // 1 >= r 表明本次分解任务完成, break
          if l >= r {
             break
          }
          // 交换
          temp = array[l]
          array[l] = array[r]
          array[r] = temp
          // 优化
          if array[l] == pivot {
             r--
          }
          if array[r] == pivot {
             l++
          }
       }
       // 如果  1== r, 再移动下
       if l == r {
          l++
          r--
       }
       // 向左递归
       if left < r {
          QuickSort(left, r, array)
       }
       // 向右递归
       if right > l {
          QuickSort(l, right, array)
       }
    }
    
    func main() {
       var arr [24000000]int
       for i := 0; i < 24000000; i++ {
          arr[i] = rand.Intn(900000)
       }
       start := time.Now().Unix()
       //调用快速排序
       QuickSort(0, len(arr)-1, &arr)
       end := time.Now().Unix()
       fmt.Printf("快速排序法耗时%d秒", end-start)
    }

## 2 测试 ##

> 快速排序法耗时3秒

# 四 比较结果 #

> 选择排序 80000 条数据耗时 4秒。
> 
> 插入排序 80000 条数据耗时 1秒。
> 
> 快速排序 24000000 条数据耗时 3秒。
> 
> 快速排序优于插入排序，插入排序优于选择排序。