目錄
1.?堆排序的基礎知識
1.1?大頂堆&&小頂堆?
1.2?向下調整算法
1.3?物理結構與邏輯結構的關系
2.?堆排序詳解
2.1?堆排序整體思路?
2.2?思路詳解
2.2.1?建堆
2.2.2?大堆or小堆
2.2.3?輸出數(shù)據(jù)
3.?時間復雜度分析
4.?完整代碼
?5.?彩蛋
1.?堆排序的基礎知識
堆排序（Heap?Sort）就是對直接選擇排序的一種改進。此話怎講呢？直接選擇排序在待排序的n個數(shù)中進行n-1次比較選出最大或者最小的，但是在選出最大或者最小的數(shù)后，并沒有對原來的序列進行改變，這使得下一次選數(shù)時還需要對全部數(shù)據(jù)進行比較，效率大大降低。
堆排序算法是Floyd和Williams在1964年共同發(fā)明的，同時他們發(fā)明了“堆”這種數(shù)據(jù)結構。
1.1?大頂堆&&小頂堆?
對于待排序的數(shù)組元素，我們可以將它的邏輯結構看成二叉樹。滿足某種條件的這種邏輯結構就是堆啦。
顯然，這是一棵完全二叉樹。那么某種條件是啥呢？
堆是具有下列性質的完全二叉樹：每個節(jié)點的值都大于或等于其左右孩子節(jié)點的值，稱為：大頂堆（大堆）；或者每個節(jié)點的值都小于或等于其左右孩子節(jié)點的值，稱為小頂堆（小堆）。?
?
1.2?向下調整算法
使用該算法的前提是該節(jié)點的左右子樹要么都是大堆，要么都是小堆。
該算法就是將該節(jié)點與左右子樹的節(jié)點進行比較，重新構建成一個大堆或者小堆。
1.3?物理結構與邏輯結構的關系
假設我們有了一個待排序的數(shù)組，并且構建好了他的邏輯結構，怎么能通過孩子找到雙親，或者通過雙親找到左右孩子呢？
先看公式：?parent = (child - 1) / 2 ;
? ? ? ? ? ? ? ? ? ?leftchild = parent * 2 + 1 ;
? ? ? ? ? ? ? ? ? ?rightchild = parent * 2 + 2 ;
? ? ? ? ? ? ? ? ? ?rightchild = leftchild + 1；
有了這個公式，左孩子，右孩子，雙親的下標知道一個就可以求其他兩個啦！
?文章來源地址http://www.zghlxwxcb.cn/news/detail-777647.html
2.?堆排序詳解
是的，堆排序就是通過建堆的方式來彌補直接選擇排序的缺陷滴。?
2.1?堆排序整體思路?
1）：給出待排序的數(shù)組，咱們腦補一個邏輯結構，然后將該邏輯結構整體調整為大堆或者小堆。?
2）：?留個問題：升序是構建大堆還是小堆呢？提示：請參考直接選擇排序的缺陷，以及堆排序如何彌補該缺陷的。搞清楚這個問題后排序即可。
3）：打印輸出數(shù)據(jù)。
2.2?思路詳解
2.2.1?建堆
以大堆為例哈：既然前面都鋪墊了向下調整算法，你們肯定猜到了是通過該算法來建堆啦。
注意該算法的使用前提：要求左右子樹都是大堆。怎么辦呢？聰明如你們，我們從邏輯結構的后面往前面用該算法不就行啦??！
?
/// <summary>
/// 交換數(shù)組元素
/// </summary>
/// <param name="pa">被交換的元素a</param>
/// <param name="pb">被交換的元素b</param>
void Swap(int* pa, int* pb)
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
/// <summary>
/// 對邏輯結構進行向下調整，構建大堆
/// </summary>
/// <param name="arr">數(shù)組首元素地址</param>
/// <param name="n">數(shù)組大小</param>
/// <param name="root">要調整的節(jié)點</param>
void AdjustDown(int* arr, int n, int root)
{
//雙親的下標
int parent = root;
//較大孩子的下標，默認為左孩子
int child = parent * 2 + 1;
//如果孩子的下標不越界，進入循環(huán)
while (child < n)
{
//如果右孩子存在（下標沒越界），并且右孩子大于左孩子，更新child
if (child + 1 < n && arr[child + 1] > arr[child])
{
child = child + 1;
}
//如果較大的孩子大于雙親，交換
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
//改變parent的下標如果滿足條件繼續(xù)向下調整
parent = child;
child = parent * 2 + 1;
}
//如果較大的孩子不大于雙親，root節(jié)點的大堆構建完畢
else
{
break;
}
}
}
/// <summary>
/// 堆排序函數(shù)
/// </summary>
/// <param name="arr">數(shù)組首元素地址</param>
/// <param name="n">數(shù)組大小</param>
void HeapSort(int* arr, int n)
{
//循環(huán)從后面往前面對需要的數(shù)組元素使用向下調整算法
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
}2.2.2?大堆or小堆
以升序為例：建大堆完成后就是這個樣子啦：9, 8, 6, 7, 3, 1, 2, 4, 5, 0 ；
? ? ? ? ? ? ? ? ? ? ? 建小堆完成后就是這個樣子：0, 3, 1, 5, 4, 2, 9, 7, 8, 6 ；
建小堆只需要將AdjustDown里面的兩個if語句的大于改成小于。
2.2.3?輸出數(shù)據(jù)
這部分比較簡單，不多分析。?
3.?時間復雜度分析
堆排序的時間復雜度分析，應該是排序算法中最復雜的，需要具備高中的基礎知識！?。?！
?
?
4.?完整代碼
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
/// <summary>
/// 交換數(shù)組元素
/// </summary>
/// <param name="pa">被交換的元素a</param>
/// <param name="pb">被交換的元素b</param>
void Swap(int* pa, int* pb)
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
/// <summary>
/// 對邏輯結構進行向下調整，構建大堆
/// </summary>
/// <param name="arr">數(shù)組首元素地址</param>
/// <param name="n">數(shù)組大小</param>
/// <param name="root">要調整的節(jié)點</param>
void AdjustDown(int* arr, int n, int root)
{
//雙親的下標
int parent = root;
//較大孩子的下標，默認為左孩子
int child = parent * 2 + 1;
//如果孩子的下標不越界，進入循環(huán)
while (child < n)
{
//如果右孩子存在（下標沒越界），并且右孩子大于左孩子，更新child
if (child + 1 < n && arr[child + 1] > arr[child])
{
child = child + 1;
}
//如果較大的孩子大于雙親，交換
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
//改變parent的下標如果滿足條件繼續(xù)向下調整
parent = child;
child = parent * 2 + 1;
}
//如果較大的孩子不大于雙親，root節(jié)點的大堆構建完畢
else
{
break;
}
}
}
/// <summary>
/// 打印數(shù)組元素
/// </summary>
/// <param name="arr">數(shù)組首元素地址</param>
/// <param name="n">數(shù)組元素個數(shù)</param>
void PrintArray(int* arr, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
/// <summary>
/// 堆排序函數(shù)
/// </summary>
/// <param name="arr">數(shù)組首元素地址</param>
/// <param name="n">數(shù)組大小</param>
void HeapSort(int* arr, int n)
{
//循環(huán)從后面往前面對需要的數(shù)組元素使用向下調整算法
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
//用來控制向下調整時的數(shù)組元素個數(shù)
int end = n - 1;
while (end > 0)
{
//交換元素，獲得最大值
Swap(&arr[0], &arr[end]);
//進行向下調整, 因為開始end為n-1嘛
AdjustDown(arr, end, 0);
//去除較大值
--end;
}
}
int main()
{
//待排序的數(shù)組
int arr[] = { 6,4,2,8,3,1,9,7,5,0 };
//調用主體函數(shù)
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
//打印數(shù)據(jù)
PrintArray(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}?5.?彩蛋
為了直觀的比較幾大排序算法的快慢，我們可以設計程序以毫秒數(shù)來量化排序的快慢。
?
文章來源：http://www.zghlxwxcb.cn/news/detail-777647.html
?
到了這里，關于十大經典排序算法----堆排序（超詳細）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
