Golang實現基本排序算法

排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

冒泡排序

func BubbleSort(vector []int) {
    fmt.Println("BubbleSort")
    fmt.Println(vector)
    for i := 0; i < len(vector); i++ {
        tag := true // 為了剪枝
        // 每一趟將最大的數冒泡
        for j := 0; j < len(vector)-i-1; j++ {
            if vector[j] > vector[j+1] { /*vector[j] < vector[j+1]*/
                temp := vector[j]
                vector[j] = vector[j+1]
                vector[j+1] = temp
                tag = false
            }
        }
        if tag {
            break //0~len(vector)-i沒有發生交換說明已經有序
        }
        fmt.Println(vector)
    }
}

插入排序

func InsertSort(vector []int) {
    fmt.Println("InsertSort")
    fmt.Println(vector)
    for i := 1; i < len(vector); i++ {
        // 每一趟不滿足條件就選擇i為哨兵保存，將哨兵插入0~i-1有序序列（0~i-1始終是有序的）
        if vector[i] < vector[i-1] { /*vector[i] > vector[i-1]*/
            temp := vector[i]
            //后移直到找到哨兵合適的位置
            j := i - 1
            for ; j >= 0 && vector[j] > temp; j-- { /*vector[j] < temp*/
                vector[j+1] = vector[j]
            }
            //插入位置前后都是有序的，最后也是有序的
            vector[j+1] = temp
        }
        fmt.Println(vector)
    }
}

選擇排序

func SelectSort(vector []int) {
    fmt.Println("SelectSort")
    fmt.Println(vector)
    for i := 0; i < len(vector); i++ {
        // 選擇最小的元素
        k := i
        for j := i + 1; j < len(vector); j++ {
            if vector[k] > vector[j] {
                k = j
            }
        }
        // 交換
        if k != i {
            temp := vector[i]
            vector[i] = vector[k]
            vector[k] = temp
        }
        fmt.Println(vector)
    }
}

二元選擇排序

func BinarySelectSort(vector []int) {
    fmt.Println("SelectSort")
    fmt.Println(vector)
    n := len(vector)
    for i := 0; i < n/2; i++ {
        // 選擇最小的元素和最大元素
        k := i
        t := n - i - 1
        for j := i + 1; j <= n-i-1; j++ {
            if vector[k] > vector[j] {
                k = j
            }
            if vector[t] < vector[j] {
                t = j
            }
        }
        // 交換
        if k != i {
            temp := vector[i]
            vector[i] = vector[k]
            vector[k] = temp
        }
        if t != n-i-1 {
            temp := vector[n-i-1]
            vector[n-i-1] = vector[t]
            vector[t] = temp
        }
        fmt.Println(vector)
    }
}

快速排序

簡單的說快速排序就是挖坑填數然后分治，公認效率最好，這個必須會

func QuickSort(vector []int, low, hight int) {
    fmt.Println(vector)
    if low < hight {
        i := low
        j := hight
        temp := vector[low] // 開始挖坑填數
        for i < j {
            for i < j && vector[j] >= temp {
                j--
            }
            vector[i] = vector[j]
            for i < j && vector[i] <= temp {
                i++
            }
            vector[j] = vector[i]
        }
        vector[i] = temp
        QuickSort(vector, low, i-1) // 分治
        QuickSort(vector, i+1, hight)
    }
}

常見問題，已知序列WAUSTHKO，將第一個數作W為基數，問：

1，第一趟后的序列是多少？假設遞歸同時進行

1），OAUSTHKW

2），KAHOTSUW

3），HAKOSTUW

4），AHKOSTUW

2，排序過程中那些數會被作為選基數？

以上標記的都是：W，O，K、T，H

3，基數的選擇直接影響到效率，同時排序末尾顯然有效率問題，可以用其他算法替換。

來自：http://my.oschina.net/xlplbo/blog/343768