C說話完成基於最年夜堆和最小堆的堆排序算法示例。本站提示廣大學習愛好者：（C說話完成基於最年夜堆和最小堆的堆排序算法示例）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話完成基於最年夜堆和最小堆的堆排序算法示例正文
堆界說
堆現實上是一棵完整二叉樹，其任何一非葉節點知足性質：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]（小頂堆）或許：Key[i]>=Key[2i+1]&&key>=key[2i+2]（年夜頂堆）
即任何一非葉節點的症結字不年夜於或許不小於其閣下孩子節點的症結字。
堆排序的思惟
應用年夜頂堆(小頂堆)堆頂記載的是最年夜症結字(最小症結字)這一特征，使得每次從無序當選擇最年夜記載(最小記載)變得簡略。
這裡以最年夜堆為基本，其根本思惟為：
1.將初始待排序症結字序列(R1,R2....Rn)構建成年夜頂堆，此堆為初始的無序區；
2.將堆頂元素R[1]與最初一個元素R[n]交流，此時獲得新的無序區(R1,R2,......Rn-1)和新的有序區(Rn),且知足R[1,2...n-1]<=R[n];
3.因為交流後新的堆頂R[1]能夠違背堆的性質，是以須要對以後無序區(R1,R2,......Rn-1)調劑為新堆，然後再次將R[1]與無序區最初一個元故舊換，獲得新的無序區(R1,R2....Rn-2)和新的有序區(Rn-1,Rn)。赓續反復此進程直到有序區的元素個數為n-1，則全部排序進程完成。
C說話完成
1.基於最年夜堆完成升序排序
// 初始化堆
void initHeap(int a[], int len) {
// 從完整二叉樹最初一個非子節點開端
// 在數組中第一個元素的索引是0
// 第n個元素的左孩子為2n+1，右孩子為2n+2，
// 最初一個非子節點地位在(n - 1) / 2
for (int i = (len - 1) / 2; i >= 0; --i) {
adjustMaxHeap(a, len, i);
}
}
void adjustMaxHeap(int a[], int len, int parentNodeIndex) {
// 若只要一個元素，那末只能是堆頂元素，也沒有需要再排序了
if (len <= 1) {
return;
}
// 記載比父節點年夜的左孩子或許右孩子的索引
int targetIndex = -1;
// 獲得左、右孩子的索引
int leftChildIndex = 2 * parentNodeIndex + 1;
int rightChildIndex = 2 * parentNodeIndex + 2;
// 沒有左孩子
if (leftChildIndex >= len) {
return;
}
// 有左孩子，然則沒有右孩子
if (rightChildIndex >= len) {
targetIndex = leftChildIndex;
}
// 有左孩子和右孩子
else {
// 取左、右孩子二者中最年夜的一個
targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
// 只要孩子比父節點的值還要年夜，才須要交流
if (a[targetIndex] > a[parentNodeIndex]) {
int temp = a[targetIndex];
a[targetIndex] = a[parentNodeIndex];
a[parentNodeIndex] = temp;
// 交流完成後，有能夠會招致a[targetIndex]結點所構成的子樹不知足堆的前提，
// 若不知足堆的前提，則調劑之使之同樣成為堆
adjustMaxHeap(a, len, targetIndex);
}
}
void heapSort(int a[], int len) {
if (len <= 1) {
return;
}
// 初始堆成無序最年夜堆
initHeap(a, len);
for (int i = len - 1; i > 0; --i) {
// 將以後堆頂元素與最初一個元故舊換，包管這一趟所查找到的堆頂元素與最初一個元故舊換
// 留意：這裡所說的最初不是a[len - 1]，而是每趟的規模中最初一個元素
// 為何要加上>0斷定？每次不是說堆頂必定是最年夜值嗎？沒錯，每趟調劑後，堆頂是最年夜值的
// 然則，因為len的規模赓續地減少，招致某些特別的序列湧現異常
// 好比說，5, 3, 8, 6, 4序列，當調劑i=1時，曾經調劑為3,4,5,6,8序列，曾經有序了
// 然則招致了a[i]與a[0]交流，因為釀成了4,3,5,6,8反而釀成無序了!
if (a[0] > a[i]) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
}
// 規模釀成為：
// 0...len-1
// 0...len-1-1
// 0...1 // 停止
// 個中，0是堆頂，每次都是找出在指定的規模內比堆頂還年夜的元素，然後與堆頂元故舊換
adjustMaxHeap(a, i - 1, 0);
}
}
2.基於最小堆完成降序排序
// 初始化堆
void initHeap(int a[], int len) {
// 從完整二叉樹最初一個非子節點開端
// 在數組中第一個元素的索引是0
// 第n個元素的左孩子為2n+1，右孩子為2n+2，
// 最初一個非子節點地位在(n - 1) / 2
for (int i = (len - 1) / 2; i >= 0; --i) {
adjustMinHeap(a, len, i);
}
}
void adjustMinHeap(int a[], int len, int parentNodeIndex) {
// 若只要一個元素，那末只能是堆頂元素，也沒有需要再排序了
if (len <= 1) {
return;
}
// 記載比父節點年夜的左孩子或許右孩子的索引
int targetIndex = -1;
// 獲得左、右孩子的索引
int leftChildIndex = 2 * parentNodeIndex + 1;
int rightChildIndex = 2 * parentNodeIndex + 2;
// 沒有左孩子
if (leftChildIndex >= len) {
return;
}
// 有左孩子，然則沒有右孩子
if (rightChildIndex >= len) {
targetIndex = leftChildIndex;
}
// 有左孩子和右孩子
else {
// 取左、右孩子二者中最上的一個
targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
// 只要孩子比父節點的值還要小，才須要交流
if (a[targetIndex] < a[parentNodeIndex]) {
int temp = a[targetIndex];
a[targetIndex] = a[parentNodeIndex];
a[parentNodeIndex] = temp;
// 交流完成後，有能夠會招致a[targetIndex]結點所構成的子樹不知足堆的前提，
// 若不知足堆的前提，則調劑之使之同樣成為堆
adjustMinHeap(a, len, targetIndex);
}
}
void heapSort(int a[], int len) {
if (len <= 1) {
return;
}
// 初始堆成無序最小堆
initHeap(a, len);
for (int i = len - 1; i > 0; --i) {
// 將以後堆頂元素與最初一個元故舊換，包管這一趟所查找到的堆頂元素與最初一個元故舊換
// 留意：這裡所說的最初不是a[len - 1]，而是每趟的規模中最初一個元素
// 為何要加上>0斷定？每次不是說堆頂必定是最小值嗎？沒錯，每趟調劑後，堆頂是最小值的
// 然則，因為len的規模赓續地減少，招致某些特別的序列湧現異常
// 好比說，5, 3, 8, 6, 4序列，當調劑i=1時，曾經調劑為3,4,5,6,8序列，曾經有序了
// 然則招致了a[i]與a[0]交流，因為釀成了4,3,5,6,8反而釀成無序了!
if (a[0] < a[i]) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
}
// 規模釀成為：
// 0...len-1
// 0...len-1-1
// 0...1 // 停止
// 個中，0是堆頂，每次都是找出在指定的規模內比堆頂還小的元素，然後與堆頂元故舊換
adjustMinHeap(a, i - 1, 0);
}
}
3.C說話版測試
年夜家可以測試一下：
// int a[] = {5, 3, 8, 6, 4};
int a[] = {89,-7,999,-89,7,0,-888,7,-7};
heapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
NSLog(@"%d", a[i]);
}
