Go语言用堆排序的方法进行一千万个int随机数排序.

fyxichen · · 1747 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

上篇文章用的是quicksort方法排序,但是如果用快速排序法对重复率很高的slice排序的时候,时间复杂度会激增,速度相当慢
所以尝试了一下堆排序,实验结果,感觉挺好的.下面是代码,大家可以参考一下,这个是建立的大顶堆.
二叉树的特性:
    最后一个非叶子节点 : root = length/2(当length为奇数的时候root向下取整) 在GO语言中的索引位置:root - 1,
    左右孩子节点:child_l = 2*root,索引位置:child_l-1,右孩子的节点: 2*root+1 索引位置.

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	Num := 10000000
	var list []int
	for i := Num; i > 0; i-- {
		list = append(list, rand.Intn(10000))
	}   //生成一千万个0---10000的随机数.
	length := len(list)
	for root := length/2 - 1; root >= 0; root-- {
		sort(list, root, length)
	} //第一次建立大顶堆
	for i := length - 1; i >= 1; i-- {
		list[0], list[i] = list[i], list[0]
		sort(list, 0, i)
	}  //调整位置并建并从第一个root开始建堆.如果不明白为什么,大家多把图画几遍就应该明朗了
	fmt.Println(list)
}
func sort(list []int, root, length int) {
	for {
		child := 2*root + 1 
		if child >= length {
			break
		}   
		if child+1 < length && list[child] < list[child+1] {
			child++ //这里重点讲一下,就是调整堆的时候,以左右孩子为节点的堆可能也需要调整
		}
		if list[root] > list[child] {
			return
		}
		list[root], list[child] = list[child], list[root]
		root = child
	}
}



有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:fyxichen

查看原文:Go语言用堆排序的方法进行一千万个int随机数排序.

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1747 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传