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

上篇文章用的是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
	}
}

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2016-03-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯数据库技术

如何利用红黑树实现排名?

26830
来自专栏吴伟祥

UML 类图介绍 转

Unified Modeling Language (UML)又称统一建模语言或标准建模语言,是始于1997年一个OMG标准,它是一个支持模型化和软件系统开发的...

9010
来自专栏ACM算法日常

交错字符串(动态规划)- leetcode 97

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

17610
来自专栏前端儿

重建二叉树

题目很简单,给你一棵二叉树的后序和中序序列,求出它的前序序列(So easy!)。

26010
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

17300
来自专栏Python小屋

Python求解一元二次方程根

本文使用Python实现一元二次方程求根公式,主要演示运算符和几个内置函数的用法,封面图片与本文内容无关。 def root(a, b, c, highmidd...

43940
来自专栏计算机视觉与深度学习基础

Leetcode 81 Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed...

20790
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

458100
来自专栏程序员互动联盟

【专业技术】Android平台下使用OpenGL

存在问题: 安卓平台下如何使用opengl? 解决方案: 1、GLSurfaceView GLSurfaceView是Android应用程序中实现OpenGl画...

39860
来自专栏生信技能树

(11)仿写bowtie-生信菜鸟团博客2周年精选文章集

然后仿写了bowtie,对我的编程技术提高非常有帮助。目录如下: 自己动手写bowtie第一讲:BWT算法详解并建立索引 自己动手写bowtie第二讲:优化索引...

37660

扫码关注云+社区

领取腾讯云代金券