选择排序、插入排序以及快速排序性能比较：

测试数据，选择排序和插入排序的数据：容量为100000的随机数组，快速排序的为容量为1000万的随机数组；

选择排序：

• 代码：

package main

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

//编写函数selectSort，完成排序；
func SelectSort(arr *[100000]int) {

    //标准的访问方式
    // (*arr)[1] = 600  <==> arr[1] = 600,编译器底层优化的功劳；
    // arr[1] = 600

    //1.先完成将第一个最大值和arr[0] ==> 先易后难；
    //假设 arr[0] 就是最大值；
    for j := 0; j < len(arr)-1; j++ {
        max := arr[j]
        maxIndex := j
        //遍历后面，1---[len(arr)-1] 比较；
        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() {

    // //定义一个数组，从大到小排序
    // arr := [6]int{10, 34, 19, 100, 80, 789}
    // fmt.Println("排序前:", arr)
    var arr [100000]int
    for i := 0; i < 100000; i++ {
        arr[i] = rand.Intn(900000)
    }

    start := time.Now().Unix()
    SelectSort(&arr)
    end := time.Now().Unix()

    fmt.Printf("选择排序耗时=%d秒\n", end-start) //选择排序耗时=4秒
    // fmt.Println("排序后:", arr)
}

• 运行结果：

sslinux@sslinux:$ go run selectsort.go
选择排序耗时=8秒

插入排序

• 代码：

package main

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

//InsertSort 插入排序实现
func InsertSort(arr *[100000]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)
    }

    /*
        //完成第1次，给第2个元素找到合适的位置并插入；
        insertVal := arr[1]
        insertIndex := 1 - 1 //下标

        //从大到小：
        for insertIndex >= 0 && arr[insertIndex] < insertVal {
            arr[insertIndex+1] = arr[insertIndex] //数据后移
            insertIndex--
        }
        //插入
        if insertIndex+1 != 1 {
            arr[insertIndex+1] = insertVal
        }
        fmt.Println("第1次插入后", *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() {
    var arr [100000]int
    for i := 0; i < 100000; i++ {
        arr[i] = rand.Intn(900000)
    }

    start := time.Now().Unix()
    InsertSort(&arr)
    end := time.Now().Unix()

    fmt.Printf("插入排序耗时=%d秒\n", end-start) //插入排序耗时=1秒
}

• 运行结果：

sslinux@sslinux$ go run insertionsort.go
插入排序耗时=2秒

快速排序

• 代码：

package main

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

//QucckSort，快速排序函数
//说明：
//1.left 表示数组左边的下标；
//2.right 表示数组右边的下标；
//3.array表示要排序的数组；
func QuickSort(left int, right int, array *[10000000]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--
        }

        // l >= 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++
        }
    }

    // 如果 l == r,再移动一下； 如果没有本判断，程序会卡在r==l的情况下；
    if l == r {
        l++
        r--
    }

    //向左递归
    if left < r {
        QuickSort(left, r, array)
    }
    //向右递归
    if right > l {
        QuickSort(l, right, array)
    }
}
func main() {
    var arr [10000000]int
    for i := 0; i < 10000000; i++ {
        arr[i] = rand.Intn(900000)
    }

    start := time.Now().Unix()
    QuickSort(0, len(arr)-1, &arr)
    end := time.Now().Unix()

    fmt.Printf("快速排序排序耗时=%d秒\n", end-start) //0秒
    // fmt.Println(arr)
}

• 运行结果：

sslinux@sslinux-$ go run quicksort.go
快速排序排序耗时=2秒

说明：

因为快速排序速度过快，所以在例子中，我将测试样本调整为10000000(一千万)，但需要的时间确实2秒。不得不说牛X

但是快速排序的速度是快，消耗的资源也不少，尤其是内存；因为递归调用需要不停的开辟新的栈空间。如果在内存资源不足的系统上运行的话，速度可能会慢很多。