我们常用的排序常见的有：
- 冒泡
- 选择
- 插入
- 希尔
- 快排
- 归并
- 堆排
- 计数
- 基数
- 桶排序
关于排序算法的时间复杂度、空间复杂度这里不加赘述，今天主要分享通过 go 性能分析工具 pprof 看看几种常见排序的性能情况。
sort.go
点击查看代码
package sort
import "math"
func BubbleSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
length := len(nums)
for i := 0; i < length; i++ {
for j := 1; j < length-i; j++ {
if nums[j-1] > nums[j] {
nums[j-1], nums[j] = nums[j], nums[j-1]
}
}
}
return nums
}
func SelectSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
length := len(nums)
for i := 0; i < length; i++ {
for j := i+1; j < length; j++ {
if nums[i] > nums[j] {
nums[i], nums[j] = nums[j], nums[i]
}
}
}
return nums
}
func InsertSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
length := len(nums)
for i:= 1; i < length; i++ {
tmp := nums[i]
j := i-1
for j >= 0 && nums[j] > tmp {
nums[j+1] = nums[j]
j--
}
nums[j+1] = tmp
}
return nums
}
func MergeSort(nums []int) []int {
merge := func(left, right []int) []int {
res := make([]int, len(left)+len(right))
var l,r,i int
// 通过遍历完成比较填入res中
for l < len(left) && r < len(right) {
if left[l] <= right[r] {
res[i] = left[l]
l++
} else {
res[i] = right[r]
r++
}
i++
}
// 如果left或者right还有剩余元素，添加到结果集的尾部
copy(res[i:], left[l:])
copy(res[i+len(left)-l:], right[r:])
return res
}
var sort func(nums []int) []int
sort = func(nums []int) []int {
if len(nums) <= 1 {
return nums
}
// 拆分递归与合并
// 分割点
mid := len(nums)/2
left := sort(nums[:mid])
right := sort(nums[mid:])
return merge(left, right)
}
return sort(nums)
}
func QuickSort(nums []int) []int {
// 快速排序，基于比较，不稳定算法，时间平均O(nlogn)，最坏O(n^2)，空间O(logn)
// 分治思想，选主元，依次将剩余元素的小于主元放其左侧，大的放右侧
// 然后取主元的前半部分和后半部分进行同样处理，直至各子序列剩余一个元素结束，排序完成
// 注意：
// 小规模数据(n<100)，由于快排用到递归，性能不如插排
// 进行排序时，可定义阈值，小规模数据用插排，往后用快排
// golang的sort包用到了快排
// (小数，主元，大数)
var quick func(nums []int, left, right int) []int
quick = func(nums []int, left, right int) []int {
// 递归终止条件
if left > right {
return nil
}
// 左右指针及主元
i, j, pivot := left, right, nums[left]
for i < j {
// 寻找小于主元的右边元素
for i < j && nums[j] >= pivot {
j--
}
// 寻找大于主元的左边元素
for i < j && nums[i] <= pivot {
i++
}
// 交换i/j下标元素
nums[i], nums[j] = nums[j], nums[i]
}
// 交换元素
nums[i], nums[left] = nums[left], nums[i]
quick(nums, left, i-1)
quick(nums, i+1, right)
return nums
}
return quick(nums, 0, len(nums)-1)
}
func HeapSort(nums []int) []int {
// 堆排序-大根堆，升序排序，基于比较交换的不稳定算法，时间O(nlogn)，空间O(1)-迭代建堆
// 遍历元素时间O(n)，堆化时间O(logn)，开始建堆次数多些，后面次数少
// 主要思路：
// 1.建堆，从非叶子节点开始依次堆化，注意逆序，从下往上堆化
// 建堆流程：父节点与子节点比较，子节点大则交换父子节点，父节点索引更新为子节点，循环操作
// 2.尾部遍历操作，弹出元素，再次堆化
// 弹出元素排序流程：从最后节点开始，交换头尾元素，由于弹出，end--，再次对剩余数组元素建堆，循环操作
// 建堆函数，堆化
var heapify func(nums []int, root, end int)
heapify = func(nums []int, root, end int) {
// 大顶堆堆化，堆顶值小一直下沉
for {
// 左孩子节点索引
child := root*2 + 1
// 越界跳出
if child > end {
return
}
// 比较左右孩子，取大值，否则child不用++
if child < end && nums[child] <= nums[child+1] {
child++
}
// 如果父节点已经大于左右孩子大值，已堆化
if nums[root] > nums[child] {
return
}
// 孩子节点大值上冒
nums[root], nums[child] = nums[child], nums[root]
// 更新父节点到子节点，继续往下比较，不断下沉
root = child
}
}
end := len(nums)-1
// 从最后一个非叶子节点开始堆化
for i:=end/2;i>=0;i-- {
heapify(nums, i, end)
}
// 依次弹出元素，然后再堆化，相当于依次把最大值放入尾部
for i:=end;i>=0;i-- {
nums[0], nums[i] = nums[i], nums[0]
end--
heapify(nums, 0, end)
}
return nums
}
func CountSort(nums []int) []int {
// 计数排序，基于哈希思想的稳定外排序算法，空间换时间，时间O(n)，空间O(n)
// 数据量大时，空间占用大
// 空间换时间，通过开辟额外数据空间存储索引号记录数组的值和数组额个数
// 思路：
// 1.找出待排序的数组的最大值和最小值
// 2.创建数组存放各元素的出现次数，先于[min, max]之间
// 3.统计数组值的个数
// 4.反向填充数组，填充时注意,num[i]=j+min，
// j-前面需要略过的数的个数，两个维度，依次递增的数j++，一个是重复的数的计数j-不变
if len(nums) == 0 {
return nums
}
// 获取最大最小值
minAndMax := func(nums []int) (min,max int) {
minNum := math.MaxInt32
maxNum := math.MinInt32
for i:=0;i<len(nums);i++ {
if nums[i] < minNum {
minNum = nums[i]
}
if nums[i] > maxNum {
maxNum = nums[i]
}
}
return minNum, maxNum
}
min_, max_ := minAndMax(nums)
// 中转数组存放遍历元素
// 空间只需要min-max
tmpNums := make([]int, max_-min_+1)
// 遍历原数组
for i:=0;i<len(nums);i++ {
tmpNums[nums[i]-min_]++
}
// 遍历中转数组填入原数组
j := 0
for i:=0;i<len(nums);i++ {
// 如果对应数字cnt=0，说明可以计入下一位数字
for tmpNums[j] == 0 {
j++
}
// 填入数字
nums[i] = j + min_
// 填一个数字，对应数字cnt--
tmpNums[j]--
}
return nums
}
sort_test.go
点击查看代码
package sort
import (
"math/rand"
"testing"
"time"
)
var (
nums = []int{4, 53, 88, 53, 52, 45, 58, 23, 96, 33}
ans = []int{4, 23, 33, 45, 52, 53, 53, 58, 88, 96}
)
func genNums(length int) []int {
rand.Seed(time.Now().UnixNano())
retNums := make([]int, length)
for i := 0; i < length; i++ {
retNums[i] = rand.Intn(100000)
}
return retNums
}
func genNumsAndAns(length int) ([]int, []int) {
nums1 := genNums(length)
nums2 := make([]int, length)
copy(nums2, nums1)
nums2 = BubbleSort(nums2)
return nums1, nums2
}
var (
largeNums, _ = genNumsAndAns(1000)
)
func TestBubbleSort(t *testing.T) {
newNums := BubbleSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkBubbleSort(b *testing.B) {
for i := 0; i < b.N; i++ {
BubbleSort(nums)
}
}
func BenchmarkBubbleSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
BubbleSort(largeNums)
}
}
func TestSelectSort(t *testing.T) {
newNums := SelectSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkSelectSort(b *testing.B) {
for i := 0; i < b.N; i++ {
SelectSort(nums)
}
}
func BenchmarkSelectSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
SelectSort(largeNums)
}
}
func TestInsertSort(t *testing.T) {
newNums := InsertSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkInsertSort(b *testing.B) {
for i := 0; i < b.N; i++ {
InsertSort(nums)
}
}
func BenchmarkInsertSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
InsertSort(largeNums)
}
}
func TestMergeSort(t *testing.T) {
newNums := MergeSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkMergeSort(b *testing.B) {
for i := 0; i < b.N; i++ {
MergeSort(nums)
}
}
func BenchmarkMergeSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
MergeSort(largeNums)
}
}
func TestQuickSort(t *testing.T) {
newNums := QuickSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkQuickSort(b *testing.B) {
for i := 0; i < b.N; i++ {
QuickSort(nums)
}
}
func BenchmarkQuickSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
QuickSort(largeNums)
}
}
func TestHeapSort(t *testing.T) {
newNums := HeapSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkHeapSort(b *testing.B) {
for i := 0; i < b.N; i++ {
HeapSort(nums)
}
}
func BenchmarkHeapSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
HeapSort(largeNums)
}
}
func TestCountSort(t *testing.T) {
newNums := CountSort(nums)
for i, v := range newNums {
if ans[i] != v {
t.Errorf("BubbleSort error!\n")
}
}
}
func BenchmarkCountSort(b *testing.B) {
for i := 0; i < b.N; i++ {
CountSort(nums)
}
}
func BenchmarkCountSort1(b *testing.B) {
for i := 0; i < b.N; i++ {
CountSort(largeNums)
}
}
test.sh-go test运行脚本
#!/bin/bash
# 每个函数跑1000次，输出profile文件，便于后面分析
go test -benchmem -bench BenchmarkBubbleSort1 -benchtime 1000x -cpuprofile=bubble.large.cpu.prof -memprofile=bubble.large.mem.prof
go test -benchmem -bench BenchmarkSelectSort1 -benchtime 1000x -cpuprofile=select.large.cpu.prof -memprofile=select.large.mem.prof
go test -benchmem -bench BenchmarkInsertSort1 -benchtime 1000x -cpuprofile=insert.large.cpu.prof -memprofile=insert.large.mem.prof
go test -benchmem -bench BenchmarkMergeSort1 -benchtime 1000x -cpuprofile=merge.large.cpu.prof -memprofile=merge.large.mem.prof
go test -benchmem -bench BenchmarkQuickSort1 -benchtime 1000x -cpuprofile=quick.large.cpu.prof -memprofile=quick.large.mem.prof
go test -benchmem -bench BenchmarkHeapSort1 -benchtime 1000x -cpuprofile=heap.large.cpu.prof -memprofile=heap.large.mem.prof
go test -benchmem -bench BenchmarkCountSort1 -benchtime 1000x -cpuprofile=count.large.cpu.prof -memprofile=count.large.mem.prof
查看profile可视化
$ pprof -http=:8080 *.large.cpu.prof
Serving web UI on http://localhost:8080
从测试的结果看，也验证了在数据量1000左右时，归并、快排、堆排性能都还可以，冒泡、选择排序则差一个数量级。
下面是测试的火焰图：
