文档章节

数据结构之堆排序

润群
 润群
发布于 2016/02/01 22:49
字数 506
阅读 89
收藏 2

秉承着对知识的渴望,以及对计算机那种强烈的好奇心。。在完成MOOC大学翁凯老师的的c语言课程后,继续探索陈越姥姥的数据结构。在此,灰常感谢MOOC这个平台,让我这个高三肆业狗能够系统的学习计算机课程(sorry,有点偏题了~~~~)

 

上班时间有时挺忙的,但是一有时间我都会进行自身知识的补充。。。

正好过年放假了,可以把剩下的排序算法学习完~~~~想想就有点激动。。。。

这一次是对一个数组进行堆排序。。。

大体思路是循环把数组调整成最大堆,然后把第一个元素放到末尾,接着将数组长度减1,直到循环结束。

本来觉得是一个很简单的算法,结果实现起来不断的报segmentation fault(当时第一反应就是数组越界了~~)。。。。

而sbulime text下c的错误调试又不熟(printf竟然都不输出了!!!!好郁闷)

只好打开terminal进行调试。。。。

果然,就是数组越界引起的。。。

最后,记录下自己的核心代码。(嗯,以自己共勉。。)

  

堆排序的算法部分:

void heap_sort(int arr[], int length){
	for (int i = length; i > 0; i--)
	{
		// build max heap....
		change_array_to_max_heap(i, arr);
		// put max element to tail...
		int temp = arr[i-1];
		arr[i-1]=arr[0];
		arr[0]=temp;
	}
		
}

 

建堆堆算法部分:

void change_array_to_max_heap(int array_size, int element[]){
	// element[0] = 0;
	// ao~~~~~~~ decreasing by step 2,for comparing the minimum heap....
	for (int i = array_size; i/2>=0; i-=2)
	{
		int min_top_heap_index = i/2;
		if (min_top_heap_index == 0 ) min_top_heap_index = 1;
		// comparing the current and the sub heap...
		for (int top_index = min_top_heap_index; top_index <= array_size; top_index*=2)
		{
			int child_left = top_index*2;
			if(child_left > array_size ) break;
			// if right element greater than left ....
			if(child_left+1<=array_size && 
				element[child_left]>element[child_left-1]){
				child_left++;
			}
			
			// if parent less than child....
			if(element[child_left-1] > element[top_index-1]){
				// printf("child:%d,top_index:%d,child_val:%d,top_val:%d\n", child_left,top_index,element[child_left-1],element[top_index-1]);
				// exchange position.....
				int temp = element[child_left-1];
				element[child_left-1] = element[top_index-1];
				element[top_index-1] = temp;
			}
		}
	}
}

 

 

好吧,顺便放上github的链接(哈哈,广告插入

heap struct

 

© 著作权归作者所有

共有 人打赏支持
润群
粉丝 0
博文 7
码字总数 2837
作品 0
深圳
程序员
私信 提问
常用数据结构以及数据结构的排序算法

数组 (Array)   在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可...

带梦想一7飞
2012/09/13
0
0
深入浅出 PHP SPL(PHP 标准库)

一、什么是spl库? SPL是用于解决典型问题(standard problems)的一组接口与类的集合。 此扩展只能在php 5.0以后使用,从PHP 5.3.0 不再被关闭,会一直有效.成为php内核组件一部份。 SPL提供了...

NateHuang
06/08
0
0
白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

长平狐
2012/12/10
83
0
白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

彭博
2012/04/12
190
0
【译】Swift算法俱乐部-插入排序

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+️,我初略统计了一下,...

Andy_Ron
09/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kubernetes里的secret最基本的用法

Secret解决了密码、token、密钥等敏感数据的配置问题,使用Secret可以避免把这些敏感数据以明文的形式暴露到镜像或者Pod Spec中。 Secret可以以Volume或者环境变量的方式使用。 使用如下命令...

JerryWang_SAP
昨天
1
0
可重入锁和非可重入锁

广义上的可重入锁指的是可重复可递归调用的锁,在外层使用锁之后,在内层仍然可以使用,并且不发生死锁(前提得是同一个对象或者class),这样的锁就叫做可重入锁。 可重入锁: ReentrantLoc...

狼王黄师傅
昨天
1
0
2018-11-20学习笔记

1. python数据类型: 给变量赋值什么样的值,变量就是什么样的类型 给变量赋值整数,变量就是整数类型 给变量赋值字符串,变量就是字符串类型 123 和“123”一样吗? 在python中 单引号 与双...

laoba
昨天
1
0
使用 React 和 Vue 创建相同的应用,他们有什么差异?

在工作中应用 Vue 之后,我对它有了相当深刻的理解。 不过,俗话说「外国的月亮比较圆」,我好奇「外国的」 React 是怎么样的。 我阅读了 React 文档并观看了一些教程视频,虽然它们很棒,但...

阿K1225
昨天
2
0
2天闭门培训|以太坊智能合约从入门到实战(北京)

2天培训 16个课时 探寻技术原理,精通以太坊智能合约开发 以太坊智能合约是现在应用的最广泛的区块链应用开发方式,HiBlock区块链社区针对以太坊智能合约的学习特别推出2天闭门研修班,通过2...

HiBlock
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部