（1）选择排序（Selection sort）
工作原理是每一次从待排序的 [数据元素] 中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完
// 选择排序
func SelectionSort(s []int)[]int {
length := len(s)
for i := 0; i < length; i++ {
// 寻找 [i : length] 区间里的最小值
for j := i + 1; j < length; j++ {
if s[i] > s[j] {
s[i], s[j] = s[j], s[i]
}
}
}
return s
}
（2）冒泡排序（Bubble Sort）
工作原理是重复走访过要排序 [数据元素]，依次比较两个相邻的元素，（如从小到大）左边的元素大于右边的元素，则两者交换位置，之后比较右，右右边元素，依此重复，直到没有相邻元素需要交换，即排序完成。
这个名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
// 冒泡排序: 基本版本,从0开始,对比相邻2个元素,如果,大的放右边,之后对比右,和右右..依次往复
func BubbleSort(arrs []int) {
length := len(arrs)
for i := 0; i < length; i++ {
for j := 1; j < length-i; j++ {
if arrs[j] < arrs[j-1] {
arrs[j], arrs[j-1] = arrs[j-1], arrs[j]
}
}
}
}
（3）插入排序（Insertion sort）
工作原理是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
如从小到大排序 arrs[ 1，6，0，5，9] 为例：
1）将第1个元素看成排好序的有序序列，对比第arrs[0]，arrs[1]元素大小，若arrs[0]>arrs[1]，则两者交换位置，这里1<6，不用改变位置
2）前两个元素为有序序列，对比arrs[1], arrs[2]元素大小，0<6,改变位置-->[1,0,6,5,9]，再对比arrs[0],arrs[1]元素大小，这里0<1，交换位置-->[0,1,6,5,9]，后续的依此类推
// 插入排序1
func InsertionSort1(s []int) []int {
length := len(s)
for i := 1; i < length; i++ {
// 寻找元素s[i]合适的插入位置
for j := i; j > 0 && s[j] < s[j-1]; j-- {
// 如果 s [j] >= s [j-1],说明 s[j]比s[j-1]以及之前的元素都大，
// s[i]已经到了合适的位置可以提前结束循环
s[j], s[j-1] = s[j-1], s[j]
}
}
return s
}
插入排序的改善，改善思路是减少元素位置交换的次数，每次将要插入的元素值s[i]取出来，
比如buf:=s[i]对比buf,s[i-1]大小，若s[i-1]大，则令s[i]=s[s-1]，之后对比buf,s[i-2]大小，
若s[i-2]大，则令s[i-1]=s[i-2],直到buf>s[j],则说明s[j+1]位置为当前buf应当插入的位置，
执行s[n+1]=buf，实现如下：
// 插入排序2：改善版本
func InsertionSort2(s []int) []int {
length := len(s)
for i := 1; i < length; i++ {
buf := s[i]
j := 0
for j = i; j > 0 && s[j-1] > buf; j-- {
s[j] = s[j-1]
}
s[j] = buf
}
return s
}
性能测试
func main() {
const count = 10
nums2 := [count]int{}
for i := 0; i < count; i++ {
nums2[i] = rand.Intn(count)
}
fmt.Println("初始数据:", nums2)
fmt.Println("----")
for i := 0; i < 4; i++ {
nums3 := nums2
nums := nums3[:]
t := time.Now()
switch i {
case 0:
fmt.Println("选择排序", sort.SelectionSort(nums))
case 1:
fmt.Println("冒泡排序", sort.BubbleSort(nums))
case 2:
fmt.Println("插入排序1", sort.InsertionSort1(nums))
case 3:
fmt.Println("插入排序2", sort.InsertionSort2(nums))
}
fmt.Println("花费时间:", t.Sub(time.Now()))
fmt.Println("----")
}
}
测试结果：
初始数据: [1 7 7 9 1 8 5 0 6 0]
----
选择排序 [0 0 1 1 5 6 7 7 8 9]
花费时间: -5.53µs
----
冒泡排序 [0 0 1 1 5 6 7 7 8 9]
花费时间: -4.029µs
----
插入排序1 [0 0 1 1 5 6 7 7 8 9]
花费时间: -3.45µs
----
插入排序2 [0 0 1 1 5 6 7 7 8 9]
花费时间: -3.423µs
加大数量，继续测试
const count = 10000
nums2 := [count]int{}
for i := 0; i < count; i++ {
nums2[i] = rand.Intn(count)
}
fmt.Println("----")
for i := 0; i < 4; i++ {
nums3 := nums2
nums := nums3[:]
t := time.Now()
switch i {
case 0:
sort.SelectionSort(nums)
fmt.Printf("选择排序")
case 1:
//sort.BubbleSort(nums)
fmt.Printf("冒泡排序")
case 2:
sort.InsertionSort1(nums)
fmt.Printf("插入排序1")
case 3:
sort.InsertionSort2(nums)
fmt.Printf("插入排序2")
}
fmt.Println("花费时间:", t.Sub(time.Now()))
fmt.Println("----")
}
测试结果：
选择排序花费时间: -167.830966ms
----
冒泡排序花费时间: -3.931µs
----
插入排序1花费时间: -30.558033ms
----
插入排序2花费时间: -25.94522ms
以上3种排序，时间复杂度都为O(n^2)
结论：插入排序的性能明显优于选择排序和冒泡排序，另外对内存地址修改较少的插入排序
速度相对快一点。
另外由于插入排序可以提前结束内循环，在排序相对有序的数据时，插入排序有很大的优势，
时间复杂度接近O(n)
网友评论