GO语言学习实战3：GO语言里常用的排序算法，冒泡、选择、插入排序

在很多面试里经常会出现的几种排序方法，这里做个算法入门案例供参考：

一、冒泡排序

冒泡排序的原理是，对给定的数组进行多次遍历，每次均比较相邻的两个数，如果前一个比后一个大，则交换这两个数。经过第一次遍历之后，最大的数就在最右侧了；第二次遍历之后，第二大的数就在右数第二个位置了；以此类推。

1.一共会len(array) - 1 次的for比较，每一次会确定一个数的位置

2.每一次For 的比较次数在逐渐减少（j < len(array)-i-1）

3.当发现前面的一个数比后面的一个数大的时候，就进行了值交换：array[j], array[j+1] = array[j+1], array[j]

var array []int  //定义一个数组切片
var order = 10000 //排序10000个随机整数，用时约125ms
for i := 0; i < order; i++ {
	array = append(array, rand.Intn(order+i)) //向切片里追加随机数
}
fmt.Println("========================> array原始数据 <========================")
fmt.Println(array)
arrayLen := len(array)
for i := 0; i < arrayLen; i++ {
	for j := 1; j < arrayLen-i; j++ { //每一次For 的比较次数在逐渐减少
		//降序（由大到小）使用>,升序（由小到大）使用<即可
		if array[j] > array[j-1] {
			array[j], array[j-1] = array[j-1], array[j] //对比成功则值交换
		}
	}
}
fmt.Println("========================> array冒泡排序后 <========================")
fmt.Println(array)

 一般情况下我们直接把for封装成函数使用。冒泡排序（排序10000个随机整数，用时约125ms） 

二、选择排序法

 选择排序的原理是，对给定的数组或者数据切片进行多次（length-1）遍历，每次均找出最大（maxIndex）的一个值的索引（if array[j] > array[maxIndex]）。

length := len(array) //统计切片数组长度
for i := 0; i < length-1; i++ {
	maxIndex := i //寻找最大的一个数，保存为索引值
	for j := i + 1; j < length; j++ {
		if array[j] > array[maxIndex] {
			maxIndex = j //每次均找出最大的一个值的索引
		}
	}
	if maxIndex != i {
		array[i], array[maxIndex] = array[maxIndex], array[i] //进行值交换
	}
	fmt.Printf("第%d次交换后结果为： %v n", i+1, array)
}
/*
第1次交换后结果为： [29 9 9 3 1 18 1 26 4 12 14 1 2 11 20 4 27 25 11 2]
第2次交换后结果为： [29 27 9 3 1 18 1 26 4 12 14 1 2 11 20 4 9 25 11 2]
第3次交换后结果为： [29 27 26 3 1 18 1 9 4 12 14 1 2 11 20 4 9 25 11 2]
第4次交换后结果为： [29 27 26 25 1 18 1 9 4 12 14 1 2 11 20 4 9 3 11 2]
第5次交换后结果为： [29 27 26 25 20 18 1 9 4 12 14 1 2 11 1 4 9 3 11 2]
第6次交换后结果为： [29 27 26 25 20 18 1 9 4 12 14 1 2 11 1 4 9 3 11 2]
第7次交换后结果为： [29 27 26 25 20 18 14 9 4 12 1 1 2 11 1 4 9 3 11 2]
第8次交换后结果为： [29 27 26 25 20 18 14 12 4 9 1 1 2 11 1 4 9 3 11 2]
第9次交换后结果为： [29 27 26 25 20 18 14 12 11 9 1 1 2 4 1 4 9 3 11 2]
*/

选择排序相比冒泡排序法性能提升的关键是先不进行值交换，先找到最大数，并且满足条件后最多会进行length-1次值交换，而冒泡最多可能出现 length 的阶乘次值交换。选择排序（排序10000个随机整数，用时约40ms）  可以看到提升了几倍的速度~

三、插入排序法

插入排序法相比上面的选择排序法速度更快，插入式排序属于内部排序法(在内存里完成)，是对将要排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的。

插入排序基本思想：把一个待排序的切片数组（有n个值）看成是一个有序表和一个无序表，开始时有序表只包含1个元素，而无序表中有n-1个元素，排序过程是每次从无序表中取出第1个元素与有序表里的排序码依次比较，然后将比较结果插入到有序表相应的排序位置。最终返回这个排序完成的有序表。

//插入排序的实现
x := 0  //统计总循环
in := 0 //统计插入次数

for i := 1; i < len(array); i++ {
	insertVal := array[i] //当前数组里的值
	insertIndex := i - 1  //找到当前数组值的前一个数组索引
	n := 0                //当前子循环计数
	for insertIndex >= 0 && array[insertIndex] < insertVal {
		array[insertIndex+1] = array[insertIndex] //使用当前的值占位
		insertIndex--                             //索引指针移动到当前位置
		n++                                       //子循环++
		x++                                       //总循环++
	}
	re := "无插入"
	//插入到有序数组里
	if insertIndex+1 != i {
		array[insertIndex+1] = insertVal //位置不一样的时候才插入
		re = "插入成功"
		in++ //插入计数++
	}
	fmt.Println("第", i, "次:", array, "循环了", n, "次，并且", re)
	x++
}
fmt.Printf("本次插入共循环了%d次，插入了%d次！n", x, in)
/*
第 1 次: [9 1 9 3 1 18 1 26 4 12 14 29 2 11 20 4 27 25 11 2] 循环了 1 次，并且 插入成功
第 2 次: [9 9 1 3 1 18 1 26 4 12 14 29 2 11 20 4 27 25 11 2] 循环了 1 次，并且 插入成功
第 3 次: [9 9 3 1 1 18 1 26 4 12 14 29 2 11 20 4 27 25 11 2] 循环了 1 次，并且 插入成功
.........

第 18 次: [29 27 26 25 20 18 14 12 11 11 9 9 4 4 3 2 1 1 1 2] 循环了 9 次，并且 插入成功
第 19 次: [29 27 26 25 20 18 14 12 11 11 9 9 4 4 3 2 2 1 1 1] 循环了 3 次，并且 插入成功

本次插入共循环了133次，插入了17次！
*/

完整代码的运行结果：https://play.golang.org/p/n7kgfbQor0S 插入排序速度快于上面2种方式。因为子循环的数据是不固定的，按条件查的才能得出子循环多少次。

四、快速排序

快速排序是这4种排序中速度最快的，但也是最难理解的算法，因为快速排序使用了左右查找并递归完成数据的排序。

快速排序（QuickSort）是对冒泡排序的一种改进，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下： 

(1)首先设定一个分界值(explodeIndex)，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边(right)，小于分界值的数据集中到数组的左边(left)。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 

(3)然后，左边(QuickSort(array, left, explodeIndex-1))和右边(QuickSort(array, explodeIndex+1, right))的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似递归处理。 

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。 

//QuickSort 传入一个切片数组(array []int)，左边为数组索引开始0，右边为数组结束（len(array)-1）
func QuickSort(array []int, left int, right int) {
	if left >= right {
		return //如果左边索引大于等于右边索引则退出
	}
	explodeIndex := left //分割索引初始为左边
	//循环的顺序为左边第2个开始到最右边结束
	for i := left + 1; i <= right; i++ {
		if array[left] >= array[i] { //如果数组最左边大于等当前位置的值
			explodeIndex++                                                //分割位置向右偏移
			array[i], array[explodeIndex] = array[explodeIndex], array[i] //然后将数组里的值交换
		}
	}
	//起始位和分割位的值交换
	array[left], array[explodeIndex] = array[explodeIndex], array[left]
	QuickSort(array, left, explodeIndex-1)  //递归中分线以左的数据
	QuickSort(array, explodeIndex+1, right) //递归中分线以右的数据
}

func main() {
	var array []int      //定义一个数组切片
	var order = 10000000 //排序100万个随机整数
	for i := 0; i < order; i++ {
		rand.Seed(time.Now().UnixNano())                //随机种子
		array = append(array, rand.Intn(order+order+i)) //向切片里追加随机数
	}
	start := time.Now()               //快速排序开始运行时间
	QuickSort(array, 0, len(array)-1) //快速排序
	fmt.Printf("对%d个数进行快速排序共耗时[%s]", order, time.Since(start))
}
//对1000000个数进行快速排序共耗时[65.8181ms]

在GO里快速排序有好几种写法，都是使用递归完成。可以根据自己理解的方式写出来。效率大同小异。最后测试了对1亿个数进行快速排序共耗时26秒。速度还是很理想的~同样的时间，冒泡排序只能处理不到21万条的数据（对210000个数进行冒泡排序共耗时[26.3403858s]），如果使用冒泡处理1亿条可能要很久了~

除非注明，网络人的文章均为原创，转载请以链接形式标明本文地址：https://www.55mx.com/post/90