Golang教程第9篇-排序

1、冒泡排序

原理:比较相邻的两个元素,如果第一个比第二个大,就交换这两个元素,对每一对相邻的元素做同样的工作,注意者所谓的每一对相邻元素会随着前面可能存在的交换工作而变化,针对所有的元素重复以上步骤,直到没有数字需要进行比较停止

对于使用go来实现这个算法,可以分为两个层面来理解该算法

  • 针对所有的元素重复进行操作,如果元素个数为n,表示循环操作需要进行n次,称其为外层循环
  • 上面每一次的循环都需要去比较完每一对相邻的元素,这需要循环m次,称其为内层循环
  • m的值等于n减去外层循环到第几次循环了

例子1:冒泡排序

package main

import (
    "fmt"
)

func bsort(a []int) {
    for i := 0;i < len(a);i++ {
        for j := 1;j < len(a) - i;j++ {
            if a[j] < a[j-1] {
                a[j],a[j-1] = a[j-1],a[j]
            } 
        }
    }
}

func main() {
    var b []int
    b = [...]{8, 7, 5, 4, 3, 10, 15}
    bsort(b[:])
    fmt.Println(b)
}

编译执行
08api89

2、选择排序

原理:一组序列,每次选择一个元素a,按照选择大的原则,比较a与其他元素的大小,如果a小就进行交换选择出序列中最大的元素,知道所有元素都一次做过a,选择工作结束

下面具体一一组数来作说明
1 2 3 4 5
首先最开始肯定是把1当作a,这个工作会循环5次,可以用下面的循环语句来表示
for i := 0;i < len(array);i++
其次对于每一次的i,都需要对其进行与剩下的元素进行比较
for j := i + 1;j < len(a);j++
每次比较完后要拿出最大的数放到位置0,也就是元素1最开始所在的位置

具体代码

package main

import (
    "fmt"
)

func ssort(a []int) {
    for i := 0;i < len(a);i++ {
        var min int = i
        for j := i + 1;j < len(a);j++ {
            if a[min] < a[j] {
                min = j
            }
        }
        a[i],a[min] = a[min],a[i]
    }
}

func main() {
    b := [...]int{1,2,3,4,5}
    ssort(b[:])
    fmt.Println(b)
}

编译执行
09api90

冒泡排序和选择排序的第二个循环为什么有这种区别呢?冒泡排序for j := 1;j < len(a) - i;j++,它是比较的两个数进行排序,完成一次大的循环后,还是要从位置为1的数为坐标开始进行相邻元素比较交换,而选择排序for j := i + 1;j < len(a);j++完成一次大的循环后,不必再从位置为1的元素开始进行比较,因为最大的数已经确定了

3、插入排序

原理:选择一个元素,以这个元素为原始有序的序列,将后面的元素按照规则依次与有序序列的每一个元素进行比较后插入

package main

import (
    "fmt"
)

func isort(a []int) {
    for i := 1;i < len(a);i++ {
        for j := i;j > 0;j-- {
            if a[j] > a[j-1] {
                break
            }
            a[j],a[j-1] = a[j-1],a[j]
        }
    }
}

func main() {
    b := [...]{1,2,3,4,6}
    isort(b[:])
    fmt.Println(b)
}

编译执行
09api91

4、快速排序

原理:找一个标杆数,称为X,然后根据X把数组的数分堆,小于X的全放左边,大于X的全放右边,就可以啦。对于实际情况呢,我们还需要考虑等于X的情况,我将其与小于归为一起,即数组排列后,形成“小于等于X” + “大于X”两部分

package main

import (
    "fmt"
)

func qsort(a []int,left,right int) {
    if left >= right {
        return
    }
    
    var := a[left]
    k := left
    for i := left +1;i <= right;i++ {
        if a[i] < val {
            a[k] = a[i]
            a[i] = a[k+1]
            k++
        }
    }
    
    
    a[k] = val
    qsort(a,left,k-1)
    qsort(a,k+1,right)
}

func main() {
    b := [...]int{6,5,4,3,2,1}
    qsort(b[:],0,len(b)-1)
    fmt.Println(b)
}