19年第33周：Go语言排序算法的实现-Golang语言

一、8款Go排序算法的实现

参考资料：https://visualgo.net/zh/sorting?slide=1
资料使用方式：看动图和右下角的文字

package mySortMethod

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

// 1, 冒泡排序
func Bubble(numbers []int) (result []int) {
    // 核心：每一次遍历, 老大往前
    // 2, 遍历N次 从第一个数作为当前的焦点一直到N-i
    // 3, 如果左边》右边，那么交换，交换过就设置标志sortedBool = False(默认为True)
    var sortedBool bool // 如果一次都不交换，那说明提前排好了
    N := len(numbers)
    indexOffset := 1 //设置遍历的偏移量 预防Index  out of range
    result = numbers
    for i := 0; i < N-indexOffset; i++ {
        sortedBool = true
        // 冒泡排序：左右冒个泡，谁大谁往前
        for j := 0; j < N-i-indexOffset; j++ {
            if numbers[j] > numbers[j+1] {
                // 左边 》右边 老大往前走
                numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
                sortedBool = false
            }
        }
        if sortedBool == true {
            // 已经提前排序好了
            result = numbers
            break
        }
    }
    return result
}

// 2, 选择排序
func SelectSort(numbers []int) (result []int) {
    // 1, 核心：每一次遍历，找一个最值(选择最小值到起点)
    N := len(numbers) // 获取长度
    indexOffset := 1
    minIndex := 0 // 最值的位置 此函数暂定最小值
    result = numbers
    for i := 0; i < N-indexOffset; i++ {
        minIndex = i
        for j := i + indexOffset; j < N; j++ {
            // 找最值
            if numbers[j] < numbers[minIndex] {
                minIndex = j // j的位置是最小
            }
        }
        // 最值交换，让最值每一次遍历都在最前
        numbers[minIndex], numbers[i] = numbers[i], numbers[minIndex]
    }
    return result
}

// 3, 插入排序
func InsertSort(numbers []int) (result []int) {
    // 核心：每遍历一次，插入一个元素到左边已经排好序的列表里
    N := len(numbers)
    indexOffset := 1
    var notSortValue int
    for i := 0 + indexOffset; i < N; i++ {
        notSortValue = numbers[i]
        for j := i - indexOffset; j > -1; j-- {
            if notSortValue < numbers[j] {
                // 没有排序的值比左边的值大：当前j的位置右移
                numbers[j+1] = numbers[j]
                numbers[j] = notSortValue
            } else {
                // 这个位置就是没有排序值的位置
                numbers[j+1] = notSortValue
                break
            }
        }

    }
    result = numbers
    return result
}

// 4, 归并排序：采用递归
func MergeSort(numbers []int) (result []int) {
    // 核心： 拆分成小子集来排序，在合并（先递归，后合并）
    return
}

// 5, 快速排序：采用递归
func QuickSort(numbers []int) (result []int) {
    result = quickSort(numbers, 0, len(numbers)-1)
    return result
}

func quickSort(numbers []int, leftIndex, rightIndex int) (result []int) {
    // 核心：选择一个轴心，将未排序分成两个集合，小集合的数都比轴心数小
    midIndex := leftIndex          // 选择最左边的为轴心点
    leftIndexTemp := leftIndex + 1 // 存储指数 = 轴心点指数 +1
    for i := leftIndex + 1; i <= rightIndex; i++ {
        if numbers[i] < numbers[midIndex] {
            // 比轴心数值小，分配到小集合
            numbers[i], numbers[leftIndexTemp] = numbers[leftIndexTemp], numbers[i]
            leftIndexTemp += 1 //左边的终点+1
        }
    }
    // 将轴心数 和 左边的终点-1交换
    numbers[leftIndexTemp-1], numbers[midIndex] = numbers[midIndex], numbers[leftIndexTemp-1]
    midIndex = leftIndexTemp - 1 // 更新轴心点

    // 对剩下继续排序
    if midIndex-1 > leftIndex {
        // 对左边的进行排序
        numbers = quickSort(numbers, leftIndex, midIndex-1)
    }
    if rightIndex > midIndex+1 {
        // 对右边的进行排序
        numbers = quickSort(numbers, midIndex+1, rightIndex)
    }

    return numbers
}

// 6, 随机快速排序
func RandomQuickSort(numbers []int) (result []int) {
    rand.Seed(time.Now().Unix()) // 填充随机中证
    result = randomQuickSort(numbers, 0, len(numbers)-1)
    return result
}

func randomQuickSort(numbers []int, leftIndex, rightIndex int) (result []int) {
    // 核心：选择一个轴心，将未排序分成两个集合，小集合的数都比轴心数小
    // 随机轴心点：就是在选择之前随机选择一个数字与第一个数字交换
    randNum := rand.Intn(rightIndex-leftIndex) + leftIndex
    numbers[randNum], numbers[leftIndex] = numbers[leftIndex], numbers[randNum]

    midIndex := leftIndex          // 选择最左边的为轴心点
    leftIndexTemp := leftIndex + 1 // 存储指数 = 轴心点指数 +1
    for i := leftIndex + 1; i <= rightIndex; i++ {
        if numbers[i] < numbers[midIndex] {
            // 比轴心数值小，分配到小集合
            numbers[i], numbers[leftIndexTemp] = numbers[leftIndexTemp], numbers[i]
            leftIndexTemp += 1 //左边的终点+1
        }
    }
    // 将轴心数 和 左边的终点-1交换
    numbers[leftIndexTemp-1], numbers[midIndex] = numbers[midIndex], numbers[leftIndexTemp-1]
    midIndex = leftIndexTemp - 1 // 更新轴心点

    // 对剩下继续排序
    if midIndex-1 > leftIndex {
        // 对左边的进行排序
        numbers = randomQuickSort(numbers, leftIndex, midIndex-1)
    }
    if rightIndex > midIndex+1 {
        // 对右边的进行排序
        numbers = randomQuickSort(numbers, midIndex+1, rightIndex)
    }

    return numbers
}

// 7, 计数排序
func CountSort(numbers []int) (result []int) {
    // 尚未实现
    return
}

// 8, 基数排序
func RadixSort(numbers []int) (result []int) {
    // 核心：桶子法 先进先出队列 0-9
    N := len(numbers)
    var radixQueue2D [10][]int
    maxDigit := getMaxDigit(getMax(numbers)) // 获取最大的位数
    // 遍历每一个位数
    for i := 1; i <= maxDigit; i++ {
        // 放入桶中：吧所有的数值放入对应的桶中
        for j := 0; j < N; j++ {
            num := getNDigit(numbers[j], i)
            // 插入数值到对应的桶里
            radixQueue2D[num] = append(radixQueue2D[num], numbers[j])
        }
        // 从桶中取出：吧所有的数值按照低位到高，依次取出
        numbers = make([]int, 0) // 清空数组
        for m := 0; m < 10; m++ {
            for n := 0; n < len(radixQueue2D[m]); n++ {
                if radixQueue2D[m][n] != 0 {
                    numbers = append(numbers, radixQueue2D[m][n])
                }
            }
            radixQueue2D[m] = make([]int, 0) // 清空一个桶
        }
    }
    return numbers
}

// 获取最大值
func getMax(numbers []int) (maxNum int) {
    maxNum = numbers[0]
    for i := 0; i < len(numbers); i++ {
        if numbers[i] > maxNum {
            maxNum = numbers[i]
        }
    }
    return maxNum
}

// 获取一个数的最大位数
func getMaxDigit(x int) (result int) {
    num := 1
    for x/10 > 0 {
        x = x / 10
        num++
    }
    return num
}

// 获取一个数的第几位上的数
func getNDigit(num, n int) (result int) {
    // 输入 12345,4 则返回2 , 输入 123 4 0 输入 3 1 返回 3
    result = num / int(math.Pow10(n-1)) % 10
    return result
}```