堆排序

在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：

● 最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點

● 創建最大堆（Build Max Heap）：將堆中的所有數據重新排序

● 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

#include #include 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 arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); return 0;}

#include #include using namespace std;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) { //初始化，i從最後一個父節點開始調整 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); }}int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; return 0;}

def big_endian(arr, start, end): root = start while True: child = root * 2 + 1 # 左孩子 if child > end: # 孩子比最後一個節點還大 也就意味著最後一個葉子節點了 就得跳出去一次循環已經調整完畢 break if child + 1 <= end and arr[child] < arr[child + 1]: # 為了始終讓其跟子元素的較大值比較 如果右邊大就左換右，左邊大的話就默認 child += 1 if arr[root] < arr[child]: # 父節點小於子節點直接換位置 同時坐標也得換這樣下次循環可以準確判斷是否為最底層是不是調整完畢 arr[root], arr[child] = arr[child], arr[root] root = child else: # 父子節點順序正常 直接過 break def heap_sort(arr): # 無序區大根堆排序 first = len(arr) // 2 - 1 for start in range(first, -1, -1): # 從下到上，從右到左對每個節點進調整 循環得到非葉子節點 big_endian(arr, start, len(arr) - 1) # 去調整所有的節點 for end in range(len(arr) - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] # 頂部尾部互換位置 big_endian(arr, 0, end - 1) # 重新調整子節點的順序 從頂開始調整 return arr def main(): l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10] print(heap_sort(l)) # 原地排序 if __name__ == "__main__": main()