网络人

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

Kwok: 2020-11-09 12:11:04 点击:2 评论: 0

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

一、冒泡排序

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

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亿条可能要很久了~

本文地址:http://m.neter8.com/go/90.html
标签:排序冒泡

本站推荐阅读

热门点击文章