1.堆排序基本介紹:
堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法，
堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：
即子結點的鍵值或索引總是小于（或者大于）它的父節點，
堆排序的平均時間復雜度為 Ο(nlogn)
堆排序視頻詳解入口
大頂堆：
每個節點的值都大于或等于其子節點的值，在堆排序演算法中用于升序排列；
小頂堆：
每個節點的值都小于或等于其子節點的值，在堆排序演算法中用于降序排列；
2.堆的基本結構（小頂堆）：
設當前元素在陣列中以R[i]表示，那么：
(1) 它的左孩子結點是：R[2*i+1];(2) 它的右孩子結點是：R[2*i+2]
(3) 它的父結點是：R[(i-1)/2];(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]，
3.建堆（大堆）和排序（升序）：
初始無序陣列a[1, 3, 4, 5, 2, 6, 9, 7, 8, 0]：
建堆源代碼：
void AdjustDown(int* a, int n, int root)
{
//父親節點
int parent = root;
//左孩子節點
int child = parent * 2 + 1;
while(child < n) {
//在左孩子和右孩子里面找大的
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
//如果孩子結點大于父親節點進行交換
if (a[child] > a[parent]) {
int temp = a[child];
a[child] = a[parent];
a[parent] = temp;
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
建好大堆以后的原本陣列變為：a[9,8,6,7,2,1,4,3,5,0],
此時還是無序但是可通過以下操作就可將陣列變為升序：
1.堆頂（a[0])和最后一個(a[9])進行交換，
2.排除最后一個以后，對剩下的從新進行大堆調整，
3.回圈如此，直到最后一個，
4.程序展示如下：
堆排序源代碼：
void HeapSort(int *a,int n )
{
//從最后一個葉節點的父親節點開始從下往上逐個建堆，
for (int i = (n - 2) / 2; i >= 0; i--)
AdjustDown(a, n, i);
int end = n - 1;
//把堆頂資料和最后一個進行交換并對剩下的從新進行堆調整，
while (end > 0) {
int temp = a[0];
a[0] = a[end];
a[end] = temp;
AdjustDown(a, end, 0);
end--;
}
}
堆排序以后：a[0,1,2,3,4,5,6,7,8,9]，
4.源代碼：
#include<stdio.h>
//自頂向下的建堆（大堆）：
void AdjustDown(int* a, int n, int root)
{
//父親節點
int parent = root;
//左孩子節點
int child = parent * 2 + 1;
while(child < n) {
//在左孩子和右孩子里面找大的
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
//如果孩子結點大于父親節點進行交換
if (a[child] > a[parent]) {
int temp = a[child];
a[child] = a[parent];
a[parent] = temp;
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//堆排序
void HeapSort(int *a,int n )
{
//從最后一個葉節點的父親節點開始從下往上逐個建堆，
for (int i = (n - 2) / 2; i >= 0; i--)
AdjustDown(a, n, i);
int end = n - 1;
//把堆頂資料和最后一個進行交換并對剩下的從新進行堆調整，
while (end > 0) {
int temp = a[0];
a[0] = a[end];
a[end] = temp;
AdjustDown(a, end, 0);
end--;
}
}
int main()
{
int a[9] = { 12,3,65,84,76,32,4,7,78 };
HeapSort(a, 9);
for (int i = 0; i < 9; i++) {
printf("%d ", a[i]);
}
return 0;
}
5.結果展示：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249563.html
標籤：其他
上一篇：tmall-tickets-Chrome插件使用教程與功能介紹
下一篇：阿里視頻點播工具類