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次。所以，对于数据量不是很大，但记录关键字的信息量较大的排序要求，显然简单选择排序是占优的。另外，记录关键字信息量的大小对四种改进算法影响不大。

        总结：从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合也应该考虑使用不同的算法来应对它。