用Go实现冒泡排序、选择排序和快速排序的运行效率

whalert · · 513 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

//环境和语言版本：go version go1.13 windows/amd64
/********************************代码如下：*****************************************/
package main

import (
   "fmt"
   "math/rand"
   "time"
)

func main() {
   // b := [...]int{7, 89, 99, 55, 2235, 515, 88, 22, 2}
   // b2 := [...]int{7, 89, 99, 55, 2235, 515, 88, 22, 2}
   // // b3 := [...]int{7, 89, 99, 55, 2235, 515, 88, 22, 2}
   // // b4 := [...]int{7, 89, 99, 55, 2235, 515, 88, 22, 2}
   // fmt.Println(b)
   // MaoPao(b[:])
   // XuanZe(b2[:])
   // // ChaRu(b3[:])
   // fmt.Println(b)
   // fmt.Println(b2)
   var count int //= 10000 * 10 * 10
   fmt.Println("请输入要循环的次数")
   fmt.Scanf("%d", &count)
   var m1 []int
   m1 = make([]int, count)
   for i := 0; i < count; i++ {
       m1[i] = rand.Intn(count)

}
fmt.Println("生成的切片是：", m1)

   // MaoPao(m1)
   var m1c1 []int
   m1c1 = make([]int, len(m1))
   copy(m1c1, m1)

   var m1c2 []int = make([]int, len(m1))
   copy(m1c2, m1)
   var m1c3 []int = make([]int, len(m1))
   copy(m1c3, m1)
   fmt.Println("m1c1 复制到的的切片是：", m1c1)
   fmt.Println("m1c2 复制到的的切片是：", m1c2)
   fmt.Println("m1c3 复制到的的切片是：", m1c3)

   start1 := time.Now().UnixNano()
   MaoPao(m1c1)
   end1 := time.Now().UnixNano()

   start2 := time.Now().UnixNano()
   XuanZe(m1c2)
   end2 := time.Now().UnixNano()

   start3 := time.Now().UnixNano()
   quickSort(m1c3, 0, len(m1c3)-1)
   end3 := time.Now().UnixNano()

   fmt.Printf("MaoPao cost:%d MilliSeconds,%d UnixNano\n", (end1-start1)/1000/1000, (end1 - start1))
   fmt.Printf("XuanZe cost:%d MilliSeconds,%d UnixNano\n", (end2-start2)/1000/1000, (end2 - start2))
   fmt.Printf("Kuaisu cost:%d MilliSeconds,%d UnixNano\n", (end3-start3)/1000/1000, (end3 - start3))
}

//冒泡排序
func MaoPao(a []int) {
   for i := 0; i < len(a); i++ {
       for j := 0; j < len(a)-1-i; j++ {
           if a[j] < a[j+1] {
               a[j], a[j+1] = a[j+1], a[j]
           }
       }
   }
}

//选择排序
func XuanZe(a []int) {
   for i := 0; i < len(a); i++ {
       for j := i; j < len(a)-1; j++ {
           if a[i] > a[j+1] {
               a[i], a[j+1] = a[j+1], a[i]
           }
       }
   }
}

/*
   start := time.Now().UnixNano()
   fmt.Println(now.Format("2006/1/02"))
   fmt.Println(now.Format("02/1/2006 15:04"))
   fmt.Println(now.Format("2006/1/02 15:04"))
   fmt.Println(now.Format("2006年1月02日 15:04:05"))

end := time.Now().UnixNano()

fmt.Printf("cost:%d MilliSeconds\n", (end-start)/1000/1000)

*/
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}

func partition(arr []int, left, right, key int) []int { // 划分
   less := left - 1 // 小于区
   more := right + 1 // 大于区
   index := left // 下标
   for index < more {
       if arr[index] < key { // 小于划分值，就放到小于区
           swap(arr, less+1, index)
           less++ // 扩大小于区
           index++ // 比较下一个值
       } else if arr[index] > key { // 大于划分值，就放到大于区
           swap(arr, more-1, index)
           more-- // 扩大大于区；索引位置不变（因为当前值已经改变，需要再次比较）
       } else {
           index++ // 相同时，继续比较下一个
       }
   }
   // 返回等于区的位置
   return []int{less + 1, more - 1}
}

func quickSort(arr []int, left, right int) {
   if arr == nil || len(arr) < 2 {
       return
   }

   if left < right {
       part := partition(arr, left, right, arr[right]) //将数组最右边的值作为划分值
       quickSort(arr, left, part[0]-1)
       quickSort(arr, part[1]+1, right)
   }
}

有疑问加站长微信联系（非本文作者）