堆排序

内容纲要
[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]
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇