go排序之路(编程基础)

对python排序有兴趣的可以去我之前的博客查找
TopGun Python排序

冒泡排序

pupu.go（思路 每次遍历都是把最大的放在最右边,然后之后不再对它进行比较，swapped是循环的标志，最后没有前一个比后一个大的情况了，也就是说明排序结束了）

IMG_20180416_181804.jpg

package main

import "fmt"

func main(){
    items := []int{23,43,54,56,76,87,34,1,4,666,55555}
    BubbleSort(items)
    fmt.Println(items)
}

func BubbleSort(items []int){
    var(length = len(items)
        swapped = true)
    for swapped{
            swapped = false
            for index := 0; index < length-1; index++{
                if items[index] > items[index+1]{
                    items[index], items[index+1] = items[index+1], items[index]
                    swapped = true
                }
        }
        length = length - 1
    }
}

运行方式
*该方法会生成一个pupu的二进制文件，直接运行即可

go build pupu.go
./pupu

• 不会生成二进制文件， 可以直接运行

go run pupu.go

---

选择排序

第一次循环是针对所有的数据用index进行循环，第二次循环中的jindex就是一个游标而已，由他来衡量出最小的值来，然后跟其与第一次循环的index中的值进行对调

package main

import (
    "fmt"
)

func main() {
    items := []int{12, 32, 43, 45, 23, 23, 54, 23, 76, 23234, 23, 43, 23, 12, 434, 22, 1, 41}
    select_sort(items)
    fmt.Println(items)

}

func select_sort(items []int) {
    var (
        length = len(items)
    )
    for index := 0; index < length-1; index++ {
        mix_index := index
        for jindex := index; jindex < length; jindex++ {
            if items[jindex] < items[mix_index] {
                mix_index = jindex
            }
        }
        items[index], items[mix_index] = items[mix_index], items[index]
    }

}

---

插入排序

IMG_20180416_191105.jpg

图中有误 比较点是从右往左

package main

import (
    "fmt"
)

func main() {
    items := []int{3, 23, 4, 3, 2, 32, 231, 1, 32, 43, 23, 34, 43, 322, 27, 74, 87, 98}
    insert_sort(items)
    fmt.Println(items)

}

func insert_sort(items []int) {
    length := len(items)
    for index := 1; index < length; index++ {
        jindex := index
        for jindex > 0 {
            if items[jindex] < items[jindex-1] {
                items[jindex], items[jindex-1] = items[jindex-1], items[jindex]
            }
            jindex--
        }
    }

}

希尔排序

（golang中的for也可以当做while用）
希尔排序其实就是插入排序的改善版，你看他的排序核心其实就是比较 『如果前面的元素比后面的元素大 就把这两个元素换一换』，只不过是换的元素是哪几个的问题

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    shellshort(items)
    fmt.Println(items)
}

func shellshort(items []int) {
    var length = len(items)
    gap := length / 2
    for gap > 0 {
        for index := gap; index < length; index++ {
            //没想到在这里踩坑 要先判断是否大于等于0 就是要写到&&的前面才行
            for index-gap >= 0 && items[index] < items[index-gap] {
                items[index], items[index-gap] = items[index-gap], items[index]
                index -= gap
            }
        }
        gap = gap / 2
    }
}