部分排序算法总结
关于排序
通常所说的排序是指内部排序，即在内存里进行排序。相对应的有外部排序，当待排序数据比较多时，排序过程需要使用闪存。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
排序算法稳定性说明：如果待排序序列A中两个元素相等，即Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。就是保证排序前后两个相等的元素的相对顺序不变
以下为各算法的时间复杂度等对比
| 排序 | 平均 | 最优 | 最差 | 辅助空间 | 是否稳定 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn)-O(n) | 不稳定 |
| 希尔排序 | O(nlogn)-O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 不稳定 |
一些共用方法
main包用来执行，myAlgo包为具体方法实现
//以下为共用方法
//交换两个元素位置
package myAlgo
func exchange(arr []int, a int, b int) {
temp := arr[a]
arr[a] = arr[b]
arr[b] = temp
}
//返回序列最小值下标
func selectMin(arr []int, i int) int {
length := len(arr)
minKey := i
minValue := arr[minKey]
//从下标为i及之后的元素中找出值最小的元素
for k := minKey + 1; k < length; k++ {
if minValue > arr[k] {
//修改下标
minKey = k
minValue = arr[k]
}
}
return minKey
}1、冒泡排序
冒泡排序算法运行方式如下：
假设待排序序列有n个元素
第一次循环
1.从首元素开始比较相邻的元素，如果顺序不对，就把它们两个调换位置，直至最后一个，此时可以保证最后一个元素是最大的（或最小的）
2.重复以上操作，每次循环都可以将无序序列（序列无序元素数量每次循环后都在减少）最大（最小）的一个元素移至最右边，所以第k次循环后前n-k个元素是无序的，后k个元素是有序且依次递增（递减）的
示意图
package main
import (
"fmt"
"myAlgo"
)
func main() {
arr := []int{15, 45, 42, 25, 20, 63, 23, 20, 29, 100, 9}
myALgo.BubbleSort(arr);
}
package myAlgo
import "fmt"
func bubbleSort(arr []int) {
length := len(arr)
for j := length - 1; j > 0; j-- {
//外层循环控制循环次数
for i := 0; i < j; i++ {
//内层循环控制交换
if arr[i] > arr[i+1] {
//交换顺序
exchange(arr, i, i+1)
}
}
fmt.Println(arr)
}
}结果如下
2、简单选择排序
思路如下：
1.首先，找到序列中最小的那个元素，将它和第一个元素交换位置。
2.在剩下的元素中找到最小元素，将它与序列的第二个元素交换位置
3.按照以上方式如此往复，直至将整个序列排序。
因为它在不断的选择剩余元素之中的最小者，所以叫选择排序。
示意图
go实现
package main
import "fmt"
func main() {
arr := []int{15, 45, 42, 25, 20, 63, 23, 20, 29, 100, 9}
fmt.Println(arr)
myAlgo.SelectSort(arr)
}
package myAlgo
import "fmt"
func SelectSort(arr []int) {
fmt.Println("开始排序")
length := len(arr)
for i := 0; i < length; i++ {
//每循环一次都找出当前未排序元素中的最小值，和当前元素进行交换
minKey := selectMin(arr, i)
exchange(arr, i, minKey)
}
fmt.Println(arr)
}执行结果
3、直接插入排序
这个类似于玩扑克牌，一张一张的将牌拿出来插到部分已经有序序列中的合适位置，具体如下：
1.第一个元素可以看成是有序的
2.从有序序列下一个元素开始，用这个元素a从后向前，依次和有序序列元素b进行比较，如果元素a小于元素b,则将元素a插入到元素b之前，原有序序列b之后的元素均向后移动一个位置，此时生成一个新的有序序列。
3.重复操作2
示意图
go实现
package main
import (
"fmt"
"myAlgo"
)
func main() {
arr := []int{15, 45, 42, 25, 20, 63, 23, 20, 29, 100, 9}
fmt.Println(arr)
myAlgo.InsertSort(arr)
}
package myAlgo
import "fmt"
func InsertSort(arr []int) {
fmt.Println("开始排序")
//获取当前数组长度
length := len(arr)
for i := 1; i < length; i++ {
//当前值
now := arr[i]
//如果当前元素小于之前序列中的某一个元素的值，则序列从此元素向后整体移动一位
for j := i - 1; j >= 0; j-- {
if now < arr[j] {
arr[j+1] = arr[j]
arr[j] = now
} else {
arr[j+1] = now
break
}
}
fmt.Println(arr)
}
}运行结果
快速排序
算法原理：
将未排序元素根据一个作为基准的“主元”（Pivot）分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个 子序列用类似的方法进行排序。本质上，快速排序使用分治法，将问题的规模减小，然后再分别进行处理。
示意图
go实现
package main
import (
"fmt"
"myAlgo"
)
func main() {
arr := []int{40, 45, 42, 25, 20, 63, 23, 20, 50, 29, 100, 9}
fmt.Println(arr)
myAlgo.QuickSort(arr, 0, len(arr) - 1)
}
package myAlgo
import "fmt"
func QuickSort(arr []int, left int, right int) {
//设置基准数，选择第一个作为基准数
baseKey := left
baseValue := arr[baseKey]
fmt.Println("当前序列", arr[left:right+1],"基准值为",baseValue)
fmt.Println("开始排序")
i := left
j := right
for i < j {
//先从右向左找,直到找到一个小于基准数的值
for (arr[j] >= baseValue) && (i < j) {
j--
}
if i < j {
//将j的值放到i的空位上
arr[i] = arr[j]
}
//从左向右找，直到找到一个大于基准数的值
for (i < j) && (arr[i] < baseValue) {
i++
}
if i < j {
//将此时的i放到之前j产生的空位上
arr[j] = arr[i]
}
fmt.Println(arr[left:right+1])
}
arr[i] = baseValue
fmt.Println("子序列结果", arr[left:right+1])
fmt.Println("总序列", arr)
fmt.Println("--------------------")
if left < i-1 {
QuickSort(arr, left, i-1)
}
if i+1 < right {
QuickSort(arr, i+1, right)
}
}运行结果
