Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. 通用分类
  3. 正文

堆排序

2016年10月15日 994点热度 0人点赞 0条评论

内容纲要
[hide]一个关于堆排序在OJ里面出现的应用。

 

[code lang="c"] #include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b) {
int temp = *b;
*b = *a;
*a = temp;
}

void max_heapify(int arr[], int start, int end) {
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小,選擇最大的 son++; if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢,直接跳出函數
return;
else { //否則交換父子內容再繼續子節點和孫節點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}

void heap_sort(int arr[], int len) {
int i;
//初始化,i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已排好元素前一位做交換,再從新調整,直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}

int main() {
int number,ci;
scanf("%d",&number);
int arr[number+1];
for(ci=0;ci<number;ci++)
{
scanf("%d",&arr[ci]);
}
scanf("%d",&arr[number]);
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++){
if(i==len-1)
{
printf("%d\n",arr[i]);
return 0;
}
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

[/code][/hide]

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2016年10月20日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
GitHub JavaScript Java Apache php C++ hustoj C
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 15,321
  • 5,558
  • 0
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?