【golang】冒泡排序和选择排序

冒泡排序

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

package main

import "fmt"

/**
冒泡排序:将每一个数同相邻的下一个数对比，比下一个数大则交换位置.
 */
func bubble(list []int) []int {
    //用来判断是否完成了排序
    flag:=true
    len := len(list)
    for i:=0;i<len-1;i++{
        //预设这一轮没发生数的交换,在比较中，如果发生了数的交换，则把flag置为false
        flag=true
        for j:=0;j<len-1-i;j++{
            if list[j]>list[j+1]{
                //在这一轮中有数的交换
                flag=false
                list[j],list[j+1] = list[j+1],list[j]
            }
        }
        //如果这一轮中没有数的交换，就表示已经排序完成，直接跳出循环
        if flag{
            break
        }
    }
    return list
}
func main() {
    list := []int{32,31,23,45,678,32,9,12}
    fmt.Println(list)
    fmt.Println(bubble(list))
}

运行结果：

[32 31 23 45 678 32 9 12]
[9 12 23 31 32 32 45 678]

flag的作用：排序不一定会走完所有循环，有可能在中间就完成了排序。只要发现在某一轮的循环中，没有发生任何交换，就说明每一组都是前面的数比下一个数小，如此就不用再往下进行，终止循环。

选择排序

• 每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置。
• 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
• 选择排序是一个不稳定的排序算法。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法

package main

import "fmt"

/**
比较排序:
将一个元素依次与后面所有元素标记，如果大于后面的元素，就交换.
依次对除最后一个元素的所有元素执行上面的步骤
*/
func compare(list []int) []int {
    len := len(list)
    for i:=0;i<len-1;i++{
        for j:=i+1;j<len;j++{
            if list[i]>list[j]{
                list[j],list[i] = list[i],list[j]
            }
        }
    }
    return list

}
func main() {
    list := []int{32,31,23,45,678,32,9,12}
    fmt.Println(list)
    fmt.Println(compare(list))
}

运行结果：

[32 31 23 45 678 32 9 12]
[9 12 23 31 32 32 45 678]