堆排序的分析及达成
发布时间：2021-11-19 16:13:22 所属栏目：教程 来源：互联网
导读：（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。二叉堆可以分为两种形式：最大堆和最小堆。若将记录按从大到小排列，建小顶堆。若将记录按从小到大排，建大顶堆。 说明：在堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列。 算法
|
（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。二叉堆可以分为两种形式：最大堆和最小堆。若将记录按从大到小排列，建“小”顶堆。若将记录按从小到大排，建“大”顶堆。 说明：在堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列。 算法分析：时间复杂度是O(nlogn)。堆排序属于原址排序：任何时候都只需要常数个额外的元素空间存储临时数据。堆排序是不稳定的排序算法。 #include <stdio.h> #define LEFT(i) 2 * i #define RIGHT(i) 2 * i + 1 void MaxHeapAjust(int A[], int i, int len) //调整节点i满足最大堆性质 { int l = LEFT(i); int r = RIGHT(i); int largest, tmp; if (l <= len && A[l - 1] > A[i - 1]) { largest = l; } else { largest = i; } if (r <= len && A[r - 1] > A[largest - 1]) { largest = r; } if (i != largest) { tmp = A[i - 1]; A[i - 1] = A[largest - 1]; A[largest - 1] = tmp; MaxHeapAjust(A, largest, len); } } void BuildMaxHeap(int A[], int len) //构造最大堆 { for (int i = len / 2; i > 0; i--) { MaxHeapAjust(A, i, len); } } void HeapSort(int A[], int len) //堆排序 { int tmp; BuildMaxHeap(A, len); for (int i = len; i > 1; i--) { tmp = A[i - 1]; A[i - 1] = A[0]; A[0] = tmp; MaxHeapAjust(A, 1, i - 1); } } int main(void) { int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; HeapSort(A, 10); for (int i = 0; i < 10; i++) { printf("%d ", A[i]); } printf("n"); return 0; }  （编辑：南通站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
