王道計算機考研 數(shù)據(jù)結構
//堆排序
#include <stdio.h>
void swap(int* a, int* b) {
??int temp = *a;
??*a = *b;
??*b = temp;
}
void HeadAdjust(int A[], int k, int len);
// 建立大根堆
void BuildMaxHeap(int A[], int len) {
??for (int i = len / 2; i > 0; i--) //從后往前調整所有非終端結點?
????HeadAdjust(A, i, len);
}
// 將以 k 為根的子樹調整為大根堆
void HeadAdjust(int A[], int k, int len) {
??A[0] = A[k];????????????//A[0]暫存子樹的根結點?
??for(int i = 2*k;i<=len;i*=2){?//沿key較大的子結點向下篩選?
????if(i < len && A[i] < A[i + 1])
??????i++;??????????//取key較大的子結點的下標?
????if(A[0] >= A[i]) break;??// 篩選結束
????else{
??????A[k] = A[i];??????//將A[i]調整到雙親結點上?
??????k = i;?????????//修改k值，以便繼續(xù)向下篩選?
????}
??}?????
??A[k] = A[0];??????????//被篩選結點的值放入最終位置?
}
// 建立大根堆
void HeapSort(int A[], int len) {
??BuildMaxHeap(A, len);????// 初始建堆
??for (int i = len; i > 1; i--) {??// n-1趟的交換和建堆過程
????swap(&A[i], &A[1]);??????// 堆頂元素和堆底元素交換
????HeadAdjust(A, 1, i - 1);?// 把剩余的待排序元素整理成堆
??}
}
int main() {
??int A[] = { 0, 53, 9, 87, 96, 32, 65, 78, 45 };
??int len = sizeof(A) / sizeof(A[0]) - 1;
??HeapSort(A, len);
??printf("Sorted array: ");
??for (int i = 1; i <= len; i++) {
????printf("%d ", A[i]);
??}
??printf("\n");
??return 0;
}
