golang中Sort排序算法
一.启因
在使用gorm的时候,发现无法根据预加载中的数据来排序,找不到原因,再加上mysql排序在数据量大的情况下会降低查询效率,尝试了一下午后决定放弃在dao层进行排序,转到service层。
查阅资料后发现golang自带了sort包,可以用来实现排序。
二.使用方法
实现这个接口,并且可以用整数来索引即可
1 |
|
以下是我的使用方法,在model中定义新的SortUserList
1 |
|
三.源码解析
sort 包 在内部实现了四种基本的排序算法:插入排序(insertionSort)、归并排序(symMerge)、堆排序(heapSort)和快速排序(quickSort),都是DS课上学过的经典排序算法; sort 包会依据实际数据自动选择最优的排序算法。
虽然有一些细节还是看不明白,但大体思路还是看懂了
首先从sort.Sort()这个方法点进去看
1 |
|
可以看到Sort方法里有个quickSort,是快速排序的意思,但这和介绍中说的sort包会自动选择排序算法?所以继续看quickSort是什么
1 |
|
整理下思路,首先判断数据量大小(a和b)如果小于等于12的话就直接使用希尔排序
通过maxDepth来得到一个阈值,根据这个阈值和12的大小来决定使用快排还是堆排,
那么再回头看快速排序部分
1 |
|
得到b-1和c两个分界点后,先对小长度进行快速排序,再对大长度进行快速排序
1 |
|
快速排序结束后,再看希尔排序,这里分了6位为一组,排完后并没有gap减半,而是采用插入排序
我猜这里应该是因为通过大量数据实验得出,在数据长度小于12的时候,6位为一组排序后转使用插入排序的效率最高?
1 |
|
最后就是堆排序
1 |
|
大顶堆,和DS课上学的一样
四.总结
go语言sort包通过阈值巧妙地来使用多种排序算法完成排序,超快,效率高。第一次阅读语言底层源码,实际中算法的使用和课上学习的还真不一样,虽然大体方法一样,但是实际情况下往往需要注意更多的细节。算法只是工具,应用于实际情况中解决问题才是学习算法的本质,起码对于我来说是这样的,我并不想做算法工程师,我个人认为,算法固然重要,但代码水平并不仅仅取决于算法水平,就好像一个程序员是否优秀并不仅仅只取决于代码写的好不好,毕竟没有人想和不会做人的同事一起工作。