赞
踩
堆排序是一种高效的排序算法,其基本思想是利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树,通常用数组来表示。堆排序的基本步骤如下:
- 从最后一个非叶子节点开始(即A[n/2]),向下调整堆。
- 每个节点向下调整时,比较其值与其子节点的值,如果当前节点的值小于其子节点的值,则与较大的子节点交换。
- 重复上述过程,直到堆顶元素满足最大堆的性质。
代码:
// 向下调整算法,使以 parent 为根节点的堆满足大根堆性质 void AdjustDown(int* a, int parent, int n) { assert(a); int child = parent * 2 + 1; // 确保子节点不超过堆的大小 while (child < n) { // 找到左右子节点中较大的一个 if (child + 1 < n && a[child] < a[child + 1]) { ++child; } // 父节点小于较大子节点,交换父子节点位置 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; // 父节点已经大于等于子节点,退出循环 } } } // 堆排序算法 void HeapSort(int* a, int n) { // 升序排序建大根堆,降序排序建小根堆 for (int i = (n - 1) / 2; i >= 0; i--) // 从最后一个非叶子节点开始向下调整 { AdjustDown(a, i, n); // 向下调整以 i 为根节点的大根堆 } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); // 将堆顶元素(即最大值)与堆末尾元素交换 AdjustDown(a, 0, end); // 对新的堆顶进行向下调整,使其满足大根堆性质 --end; // 堆大小减 1,排除已排序好的最大值 } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。