Go 常见排序算法

算法复杂度

五种排序算法的执行时间 结果如下

冒泡排序

func BubbleSort(arr []int) []int {
    for i := 0; i < len(arr)-1; i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] > arr [j] {
                arr[i], arr[j] = arr[j], arr[i]
            }
        }
    }
    return arr
}

选择排序

func SelectSort(arr []int) []int {
    for i := 0; i < len(arr); i++ {
        min := arr[i]
        for j := i + 1; j < len(arr)-1; j++ {
            if min > arr[j] {
                min = arr[j]
            }
        }
        arr[i] = min
    }
    return arr
}

插入排序

func InsertSort(arr []int) []int {
    for i := 0; i < len(arr); i++ {
        for j := i; j > 0 && arr[j-1] > arr[j]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
    return arr
}

归并排序

func MergeSort(arr []int) []int {
    MergeArr := func(a, b []int) (c []int) {
        ind1, ind2 := 0, 0
        for ind1 < len(a) && ind2 < len(b) {
            if a[ind1] < b[ind2] {
                c = append(c, a[ind1])
                ind1++
            } else {
                c = append(c, b[ind2])
                ind2++
            }
        }
        c = append(c, a[ind1:]...)
        c = append(c, b[ind2:]...)
        return
    }

    if len(arr) < 2 {
        return arr
    }
    half := len(arr) / 2
    left := MergeSort(arr[half:])
    right := MergeSort(arr[:half])
    return MergeArr(left, right)
}

快速排序

func QuickSort(arr []int, start, end int) []int {
    if start < end {
        i, j := start, end
        key := arr[(start+end)/2]
        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if start < j {
            QuickSort(arr, start, j)
        }
        if end > i {
            QuickSort(arr, i, end)
        }
    }
    return arr
}

性能统计

package main

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

func init() {
    //以时间作为初始化种子
    rand.Seed(time.Now().UnixNano())
}

// 计算函数执行时间
func DurationTime(name string, execute func()) {
    t := time.Now()
    execute()
    duration := time.Since(t)
    fmt.Println(name, "execute time:", duration)
}

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

// 选择排序
func SelectSort(arr []int) []int {
    for i := 0; i < len(arr); i++ {
        min := arr[i]
        for j := i + 1; j < len(arr)-1; j++ {
            if min > arr[j] {
                min = arr[j]
            }
        }
        arr[i] = min
    }
    return arr
}

// 插入排序
func InsertSort(arr []int) []int {
    for i := 0; i < len(arr); i++ {
        for j := i; j > 0 && arr[j-1] > arr[j]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
    return arr
}

// 归并排序
func MergeSort(arr []int) []int {
    MergeArr := func(a, b []int) (c []int) {
        ind1, ind2 := 0, 0
        for ind1 < len(a) && ind2 < len(b) {
            if a[ind1] < b[ind2] {
                c = append(c, a[ind1])
                ind1++
            } else {
                c = append(c, b[ind2])
                ind2++
            }
        }
        c = append(c, a[ind1:]...)
        c = append(c, b[ind2:]...)
        return
    }

    if len(arr) < 2 {
        return arr
    }
    half := len(arr) / 2
    left := MergeSort(arr[half:])
    right := MergeSort(arr[:half])
    return MergeArr(left, right)
}

// 快速排序

func QuickSort(arr []int, start, end int) []int {
    if start < end {
        i, j := start, end
        key := arr[(start+end)/2]
        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }
        if start < j {
            QuickSort(arr, start, j)
        }
        if end > i {
            QuickSort(arr, i, end)
        }
    }
    return arr
}

func main() {
    length := 50000
    arr0 := make([]int, length)
    arr1 := make([]int, length)
    arr2 := make([]int, length)
    arr3 := make([]int, length)
    arr4 := make([]int, length)
    arr5 := make([]int, length)
    for i := 0; i < length; i++ {
        randNum := rand.Intn(300)
        arr0[i] = randNum
        arr1[i] = randNum
        arr2[i] = randNum
        arr3[i] = randNum
        arr4[i] = randNum
        arr5[i] = randNum
    }

    //fmt.Print(arr0)
    DurationTime("SelectSort", func() {
        SelectSort(arr1)
    })
    DurationTime("BubbleSort", func() {
        BubbleSort(arr2)
    })
    DurationTime("InsertSort", func() {
        InsertSort(arr3)
    })
    DurationTime("MergeSort", func() {
        MergeSort(arr4)
    })
    DurationTime("QuickSort", func() {
        QuickSort(arr5, 0, len(arr5)-1)
    })
}