Golang实现基本排序算法
jopen
10年前
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
冒泡排序
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