go语言实现排序算法之插入排序、冒泡排序、选择排序

Go  /  管理员 发布于 3年前   798

1.插入排序算法

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

示例代码：

package main
import (
    "fmt"
)
func insertionSort(arr []int) []int {
    for i := range arr {  //遍历切片
        preIndex := i - 1 //从第二个数开始
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]// 数字大往后移动
            preIndex -= 1
        }
        arr[preIndex+1] = current // 数字小往前移动
    }
    return arr
}
func main() {
    arr := []int{100,1,5,7,9,23,4,78,99,66,54,10,12}
    insertionSort := insertionSort(arr)
    fmt.Println("insertionSort:",insertionSort)
}

效果：

insertionSort: [1 4 5 7 9 10 12 23 54 66 78 99 100]

2.冒泡排序算法

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

示例代码：

package main
import (
    "fmt"
)
func bubbleSort(arr []int) []int {
    length := len(arr) //数据总长度（个数）
    for i := 0; i < length; i++ {
        for j := 0; j < length-1-i; j++ {
            if arr[j] > arr[j+1] {//和相邻的比
                arr[j], arr[j+1] = arr[j+1], arr[j] //对换位置
            }
        }
    }
    return arr
}
func main() {
   //切片可以是一个数组 []int [5]int [10]int  不是同一个类型
    arr := []int{100,1,5,7,9,23,4,78,99,66,54,10,12}//切片 一整个数组的切片
    bubble := bubbleSort(arr)
    fmt.Println("bubble:",bubble)
}

效果：

bubble: [1 4 5 7 9 10 12 23 54 66 78 99 100]

3.选择排序算法

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

示例代码：

package main
import (
    "fmt"
)
func selectionSort(arr []int) []int {
    length := len(arr)//切片长度
    for i := 0; i < length-1; i++ { //循环次数 总元素个数
        min := i  // 0
        for j := i + 1; j < length; j++ { //循环次数 总元素个数减一
            if arr[min] > arr[j] { //如果默认最小数大于旁边第二数
                min = j
            }
        }
        //交换位置 依次选出最小值存入arr[0] arr[1]...
        arr[i], arr[min] = arr[min], arr[i] 
    }
    return arr
}
func main() {
    arr := []int{100,1,5,7,9,23,4,78,99,66,54,10,12}
    selectionSort := selectionSort(arr)
    fmt.Println("selectionSort:",selectionSort)
}

效果：

selectionSort: [1 4 5 7 9 10 12 23 54 66 78 99 100]