golang sort

快速排序

package main

import (
    "fmt"
    //    "math/rand"
    //    "time"
)

func main() {
    var z []int = []int{20, 1, 2, 3, 21, 5, 6, 30, 31}
    fmt.Println("[]int z is : ", z)
    ll := len(z)
    sort(z, 0, ll-1)
    fmt.Println(z)

}
func sort(list []int, left, right int) {
    fmt.Println("runing quick sort , now the lst is: ", list)
    temp := list[left]
    p := left
    i, j := left, right

    for i <= j {
        //step1：j定位到从右到左第一个小于base的值（此时j右边都是大于base的数）
        for j >= p && list[j] >= temp {
            j--
        }

        //j的值赋值给目前的p，也就是i定位的值，p移动到j指向的值（p指向的值已经置在i）
        if j >= p {
            list[p] = list[j]
            p = j
        }
        //其实这是两个处理分支
        //如果i小于base，就往右移动一位（i的左边都是小于base的值），目前的指向值赋值给p指向的值（暂时存储,不管其是否大于base），等待下次step1处理
        //第一次base，i指向的值肯定小于base，但是分组后有可能大于base，所以要有list[i] <= temp这个条件
        if list[i] <= temp && i <= p {
            i++

        }
        //如果i大于base的值,就停止不动，目前的指向值赋值给p指向的值，等待下次step1循环处理
        if i <= p {
            list[p] = list[i]
            p = i
        }
        //思想就是保证i左j右大于base，p始终在两个边界来回goto
        list[p] = temp

    }
    if p-left > 1 {
        sort(list, left, p-1)
    }
    if right-p > 1 {
        sort(list, p+1, right)
    }

}

huzh@DESKTOP-LFIDO1U ~/code/prectise
$ go run quicks.go
[]int z is : [20 1 2 3 21 5 6 30 31]
runing quick sort , now the lst is: [20 1 2 3 21 5 6 30 31]
runing quick sort , now the lst is: [6 1 2 3 5 20 21 30 31]
runing quick sort , now the lst is: [5 1 2 3 6 20 21 30 31]
runing quick sort , now the lst is: [3 1 2 5 6 20 21 30 31]
runing quick sort , now the lst is: [2 1 3 5 6 20 21 30 31]
runing quick sort , now the lst is: [1 2 3 5 6 20 21 30 31]
runing quick sort , now the lst is: [1 2 3 5 6 20 21 30 31]
[1 2 3 5 6 20 21 30 31]

选择排序

package main

import "fmt"

func main() {
    lst := []int{20, 21, 1, 3, 4, 25, 34, 7, 8, 34}
    fmt.Println("len is:", len(lst))
    sort(lst)
    fmt.Println(lst)

}

func sort(lst []int) {
    for i := 0; i < len(lst); i++ {
        for j := i + 1; j < len(lst); j++ {
            if lst[i] > lst[j] {
                lst[i], lst[j] = lst[j], lst[i]
            }
        }
    }

}

$ go run select.go
len is: 10
[1 3 4 7 8 20 21 25 34 34]

 冒泡排序

package main

import "fmt"

func main() {
    lst := []int{20, 21, 1, 3, 4, 25, 34, 7, 8, 34}
    fmt.Println("len is:", len(lst))
    sort(lst)
    fmt.Println(lst)

}

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

}

huzh@DESKTOP-LFIDO1U ~/code/prectise
$ go run budd.go
len is: 10
[1 3 4 7 8 20 21 25 34 34]

 insert sort

package main

import "fmt"

func main() {
    lst := []int{20, 21, 1, 3, 4, 4, 25, 34, 7, 8, 34}
    sort(lst)
    fmt.Println(lst)
}

func sort(lst []int) {
    for i := 1; i < len(lst); i++ {
        j := i
        temp := lst[i]
        //lst[j-1] &&  j > 0 会报越界错误
        //j>0为了限制j-1>-1 =>  >=0
        for j > 0 && lst[j-1] > temp {
            lst[j] = lst[j-1]
            //j-- 定位到小值位置，小值已经后移
            j--

        }
        //此处的j等于for中的是j--后的量
        lst[j] = temp
    }

}

huzh@DESKTOP-LFIDO1U ~/code/prectise
$ go run insert.go
[1 3 4 4 7 8 20 21 25 34 34]