package mainimport "fmt"func main() {BubbleSort()SelectSort()InsertSort()MergeSort()QuickSort()HeapSort()ShellSort()
}//冒泡排序
func BubbleSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}for i := 0; i < len(str)-1; i++ {flag := falsefor j := len(str) - 1; j > i; j-- {if str[j] < str[j-1] {str[j], str[j-1] = str[j-1], str[j]flag = true}}if !flag {break}}fmt.Println("BubbleSort: ", str)
}//選擇排序
func SelectSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}for i := 0; i < len(str)-1; i++ {min := ifor j := i + 1; j <= len(str)-1; j++ {if str[j] < str[min] {min = j}}if min != i {str[i], str[min] = str[min], str[i]}}fmt.Println("SelectSort: ", str)
}//插入排序
func InsertSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}for i := 1; i <= len(str)-1; i++ {temp := str[i]j := i - 1for ; j >= 0 && str[j] > temp; j-- {str[j+1] = str[j]}str[j+1] = temp}fmt.Println("InsertSort: ", str)
}// 希爾排序   與插入排序比較，把原來按順序變成了相隔增量,增量不能小于3
func ShellSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}//increment相隔數量// for increment := len(str) / 3; increment > 0; increment /= 3 {increment := len(str)for increment > 0 {increment = increment / 3//此過程類似于插入排序的過程for i := increment; i <= len(str)-1; i++ {key := str[i]j := i - increment//按照increment，數組從j到0進行交換比較for ; j >= 0 && str[j] > key; j -= increment {str[j+increment] = str[j]}//str[j+increment] = key}}fmt.Println("ShellSort: ", str)
}//堆排序
func HeapSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}for i := len(str) / 2; i >= 0; i-- {Heap_Adjust_0(str, len(str), i)}for i := len(str) - 1; i > 0; i-- {str[i], str[0] = str[0], str[i]Heap_Adjust_0(str, i, 0)}fmt.Println("HeapSort: ", str)
}// 函數0和函數1是同一種思路，只是寫法不同// 堆調整函數0
func Heap_Adjust_0(str []int, length, index int) {parent := indexchild := 2*parent + 1for ; child < length-1; child *= 2 {if str[child] < str[child+1] {child++}if str[parent] < str[child] {str[parent], str[child] = str[child], str[parent]parent = child}}
}// 堆調整函數1
func Heap_Adjust_1(str []int, length, index int) {largest := index     // 初始化最大元素為根節點left := 2*index + 1  // 左子節點索引right := 2*index + 2 // 右子節點索引// 如果左子節點大于根節點if left < length && str[left] > str[largest] {largest = left}// 如果右子節點大于最大元素if right < length && str[right] > str[largest] {largest = right}// 如果最大元素不是根節點if largest != index {str[index], str[largest] = str[largest], str[index]// 遞歸調整受影響的子樹Heap_Adjust_2(str, length, largest)}
}//歸并排序
func MergeSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}str = Merging_Sort(str)fmt.Println("MergeSort: ", str)
}func Merging_Sort(str []int) []int {if len(str) <= 1 {return str}mid := len(str) / 2left := Merging_Sort(str[:mid])right := Merging_Sort(str[mid:])res := Merge_1(left, right)return res
}//合并函數0
func Merge_0(left, right []int) []int {result := make([]int, len(left)+len(right))i, j := 0, 0for k := 0; k < len(result); k++ {if i >= len(left) {result[k] = right[j]j++} else if j >= len(right) {result[k] = left[i]i++} else if left[i] < right[j] {result[k] = left[i]i++} else if right[j] < left[i] {result[k] = right[j]j++}}return result
}//合并函數1
func Merge_1(left, right []int) []int {//result := make([]int, 0, len(left)+len(right))var result []inti, j := 0, 0for {if i >= len(left) {result = append(result, right[j:]...)break} else if j >= len(right) {result = append(result, left[i:]...)break} else if left[i] < right[j] {result = append(result, left[i])i++} else if right[j] < left[i] {result = append(result, right[j])j++}}return result
}//快速排序
func QuickSort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}Quicking_Sort(str, 0, len(str)-1)fmt.Println("QuickSort: ", str)
}func Quicking_Sort(str []int, low, high int) {if low < high {pivot := Partition(str, low, high)Quicking_Sort(str, low, pivot-1)Quicking_Sort(str, pivot+1, high)}
}//獲取基準值函數
func Partition(str []int, low, high int) int {pivotky := str[low]for low < high {for low < high && str[low] < pivotky {low++}for low < high && str[high] > pivotky {high--}str[low], str[high] = str[high], str[low]}return low
}

排序算法的指標性能比較

????????????????????????????????????????????????????????????????????????表1

一、七種排序算法的性能指標說明：

????????（1）冒泡排序：最壞的情況，即為序列處于逆序的情況，此時需要比較的次數為n（n-1）/2;最好的情況就是序列本身有序，那么需要比較的次數為n-1次，平均o（n2）

????????（2）簡單選擇排序：無論最好最差情況，其比較次數均為n（n-1）/2，對于交換次數而言，最好的情況,交換0次，最差的情況，交換次數為n-1次，那么綜合比較和交換的次數，平均時間復雜度為o（n2）

????????（3）直接插入排序：最好的情況，即排序表本身是有序的，比較了n-1次，時間復雜度為o（n）；最壞的情況，即待排序為逆序，此時需要比較（n+2）*（n-1）/2,且移動的次數也達到最大（n+4）*（n-1）/2；如果排序記錄是隨機的，那么根據概率相同的原則，平均比較和移動次數為n2/4,因此，最壞和平均時間復雜度均為o（n2）

????????（4）希爾排序：希爾排序的好壞取決于增量的選取，究竟如何選取一個好的增量，目前仍然沒有一種最好的辦法。目前較好的情況，可以使希爾排序的時間復雜度縮減為O（n1.5）左右，最壞的情況仍然是o（n2）

????????（5）堆排序：在構建堆的過程中，因為我們是完全二叉樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的交換，對于每個非終端結點而言，其實最多進行兩次比較和互換操作，因此這個構建堆的時間復雜度為o（n）；在正式排序中，第i次取堆頂記錄重建堆需要用o（logi）的時間，并且需要取n-1次堆頂記錄，因此，重建堆的時間復雜度為o（nlogn）；所以整體而言，對于堆排序，最好，最壞和平均情況，時間復雜度均為o（nlogn）

????????（6）歸并排序：一趟歸并需要將待排序序列中所有記錄掃描一遍，需要o（n）時間，而由完全二叉樹深度可知，整個歸并排序需要進行log2n，因此，總的時間復雜度為o（nlogn），并且zhe是歸并排序最好，最壞，平均性能。此外，歸并排序過程中，需要與原始記錄序列同樣數量的存儲空間存放歸并結果以及遞歸時深度為log2n的棧空間，因此空間復雜度為o（n+logn），也就是說歸并排序是一種比較占用內存的算法。此外，歸并排序需要兩兩比較，但不存在跳躍，因此歸并排序也是一種穩定的排序算法。

????????（7）快速排序，在最優的情況下，partition每次都劃分的很均勻，這樣不斷的劃分下去，時間復雜度為o（nlogn），在最壞的情況待排序為正序或者逆序，比較次數為n（n-1）/2，最終時間復雜度為o（n2），那么平均情況為o（nlogn）。就空間復雜度而言，主要是遞歸造成的棧空間使用，最好情況，遞歸深度為o（log2n），空間復雜度也就為o（n），最壞的情況需要進行n-1遞歸調用，空間復雜度o（n），所以平均情況空間復雜度也就為o（logn）由于關鍵字的比較和交換是跳躍進行的，所以快速排序不是一種穩定的算法。

二、七種算法在各個指標上的相互比較：

接下來，從各個指標分析這七種算法的優劣：

????????（1）從算法的簡單性來看：

????????????????簡單算法：冒泡，簡單選擇，直接插入

????????????????改進算法：希爾，堆，歸并，快速

????????（2）從平均情況來看，顯然三種改進算法要好于希爾排序，遠遠勝于前三種簡單排序

????????（3）從最好情況來看，冒泡排序和直接插入排序要更好一些，也就是說，如果待排序數組總是基本有序的，應該優先考慮冒泡和直接插入排序算法

????????（4）從最壞的情況來看，堆排序和歸并排序又強于快速排序和其他簡單排序

????????（5）從空間復雜度來看，歸并排序和快速排序都有相應的空間要求，這樣，如果執行算法的軟件所處的環境非常在乎內存使用量多少，現在歸并和快排顯然不是一個很好的辦法

????????（6）從穩定性來看，歸并排序獨占鰲頭，對于非常在乎排序穩定性的應用，歸并排序是個好算法

????????（7）從待排序記錄的個數來說，待排序的個數n越小，采用簡單排序方法越合適。反之，n越大，采用改進算法越合適。這樣，我們在采用快速排序優化時，考慮增加一個閾值，當待排序數目小于閾值采用直接插入排序，否則選擇快速排序

????????（8）從表1來看，似乎簡單選擇排序是最差的算法，但也并不完全，比如，如果記錄關鍵字本身信息量比較大，此時表面其占用內存空間較大，這樣移動記錄花費的時間就越多，下面給出三種簡單排序算法此時的"移動"次數比較：

????????????????????????????????????????????????????????????????????????表2

????????你會發現，此時簡單選擇排序在最差情況就變得很有優勢，因為簡單選擇排序每次是通過與其后面的元素先一一比較，找到最小的元素，再與最小的元素進行交換，所以它的移動次數最多為n-1次。所以，對于數據量不是很大，但記錄關鍵字的信息量較大的排序要求，顯然簡單選擇排序是占優的。另外，記錄關鍵字信息量的大小對四種改進算法影響不大。

????????總結：從綜合各項指標來說，經過優化的快速排序是性能最好的排序算法，但是不同的場合也應該考慮使用不同的算法來應對它。