数据结构之堆排序
博客专区 > 润群 的博客 > 博客详情
数据结构之堆排序
润群 发表于2年前
数据结构之堆排序
  • 发表于 2年前
  • 阅读 85
  • 收藏 2
  • 点赞 1
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: heap sort......

秉承着对知识的渴望,以及对计算机那种强烈的好奇心。。在完成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
×
润群
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: