使用go实现的排序算法

go实现的部分排序算法，待整理

// algorithm project main.go
package main

import (
    "fmt"
)

func main() {
    arr := []int{50, 45, 42, 30, 25, 20, 20, 5, 60, 3, 23, 50, 29, 235, 9}
    //arr := []int{50, 235, 60}
    fmt.Println(arr)
    fmt.Println("----------")
    //直接插入排序
    //arr1 := insertSort(arr)
    //arr1 := selectSort(arr)
    //a, b := selectMinAndMax(arr, 0, 14)
    //arr1 := selectSortPlus(arr)
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

/********  冒泡排序begin ********/
func bubbleSort(arr []int) []int {
    length := len(arr)
    for j := length - 1; j > 0; j-- {
        for i := 0; i < j; i++ {
            if arr[i] > arr[i+1] {
                exchange(arr, i, i+1)
                fmt.Println(arr)
            }
        }
        fmt.Println("++++++++++")
    }
    return arr
}

/********  冒泡排序end ********/

/*******  直接插入排序begin  ********/

//注意第一次排序应该是把第一位，即索引为0的看做一个有序序列了

func insertSort(arr []int) []int {
    //获取当前数组长度
    length := len(arr)
    for i := 1; i < length; i++ {
        //当前值
        now := arr[i]
        //如果当前哨兵小于之前序列中的某一个k的值，则序列从k向后整体移动一位
        for j := i - 1; j >= 0; j-- {
            if now < arr[j] {
                arr[j+1] = arr[j]
                arr[j] = now
            } else {
                arr[j+1] = now
                break
            }
        }
        fmt.Println(arr)
    }
    return arr
}

/*******  直接插入排序end  ********/

/*******  选择排序-简单选择排序begin  ********/
//选出最小的key值
/*
@param arr 待排序数组
@param i从第i个元素获取最小值
*/
func selectMin(arr []int, i int) int {
    length := len(arr)
    minKey := i
    minValue := arr[minKey]
    //从下标为i及之后的元素中找出值最小的元素
    for k := minKey + 1; k < length; k++ {
        if minValue > arr[k] {
            //如果当前值大于之后某一元素，说明不是最小值，和之后元素交换
            minKey = k
            minValue = arr[k]

        }
    }
    return minKey
}

func exchange(arr []int, a int, b int) {
    temp := arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

//开始进行选择排序
func selectSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        //每循环一次都找出当前未排序元素中的最小值，和当前元素进行交换
        minKey := selectMin(arr, i)
        exchange(arr, i, minKey)
        fmt.Println(i, arr)
    }
    return arr
}

/*******  选择排序-简单选择排序end  ********/

/********   选择排序的改进，二元选择排序begin ********/

func selectMinAndMax(arr []int, i int, j int) (int, int) {
    //length := len(arr)
    minKey := i
    minValue := arr[minKey]
    maxKey := j
    maxValue := arr[maxKey]
    //从下标为i及之后的元素中找出值最小的元素
    for k := minKey + 1; k < j; k++ {
        if minValue > arr[k] {
            //如果当前值大于之后某一元素，说明不是最小值，和之后元素交换
            minKey = k
            minValue = arr[k]
        }
        if maxValue < arr[k] {
            maxKey = k
            maxValue = arr[k]
        }
    }
    return minKey, maxKey
}

func selectSortPlus(arr []int) []int {
    length := len(arr)
    //
    for i := 0; i <= length/2; i++ {
        //一次循环，找出最大和最小值，分别替换最大端和最小端顶头部分
        minKey, maxKey := selectMinAndMax(arr, i, length-1-i)
        exchange(arr, i, minKey)
        exchange(arr, length-1-i, maxKey)
        fmt.Println(minKey, maxKey)
    }
    return arr
}

/********   选择排序的改进，二元选择排序end ********/

/******** 快速排序begin ********/
func quickSort(arr []int, left int, right int) {
    fmt.Println(left, right)

    //设置基准数，选择第一个作为基准数
    baseKey := left
    baseValue := arr[baseKey]
    i := left
    j := right
    for i < j {
        fmt.Println(i, j)
        //先从右向左找,直到找到一个小于基准数的值
        for (arr[j] >= baseValue) && (i < j) {
            j--
        }
        if i < j {
            //将j的值放到i的空位上
            arr[i] = arr[j]
        }
        //从左向右找，直到找到一个大于基准数的值
        for (i < j) && (arr[i] < baseValue) {
            i++
        }
        if i < j {
            //将此时的i放到之前j产生的空位上
            arr[j] = arr[i]
        }
        fmt.Println(i, j)
    }
    arr[i] = baseValue
    fmt.Println(arr)
    if left < i-1 {
        quickSort(arr, left, i-1)
    }
    if i+1 < right {
        quickSort(arr, i+1, right)
    }

}

/******** 快速排序end ********/

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