使用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 ********/

本文来自:Segmentfault

感谢作者:light

查看原文:使用go实现的排序算法

• 编辑
• 预览