)
目录前言堆排序思路为什么升序 → 建大根堆降序 → 建小根堆。演示图如下代码如下练习排序的时间复杂度与空间复杂度结语前言排序算法是计算机数据处理领域最基础、最核心的一类算法广泛应用于数据检索、业务统计、任务调度等场景。常见的排序算法中冒泡排序、选择排序、插入排序时间复杂度为(O(n^2))面对大规模数据时效率低下快速排序虽平均性能优异但最坏情况下时间复杂度会退化至 (O(n^2))且属于不稳定排序。堆排序作为一种基于二叉堆数据结构实现的原地排序算法凭借稳定的 (O(nlog n)) 时间复杂度、(O(1)) 的额外空间开销弥补了上述算法的短板。它借助大根堆、小根堆的特性不断选取当前区间内的极值逐步完成元素就位。在学习堆排序的过程中非常容易出现「升序建小根堆」的直觉误区。本文从堆的底层性质出发完整讲解堆排序的原理、向上调整、向下调整、建堆逻辑与排序流程结合实例剖析升序选择大根堆、降序选择小根堆的根本原因给出可运行的 C 代码实现帮助彻底吃透堆排序。其他排序快速排序排序-快速排序Quick sort基础版-CSDN博客插入排序排序—插入排序(Insertion Sort)-CSDN博客冒泡排序与选择排序排序-选择排序Selection Sort冒泡排序Bubble Sort-CSDN博客希尔排序排序-希尔排序(Shell Sort)-CSDN博客归并排序排序-归并排序Merge Sort-CSDN博客堆排序思路堆排序利用大根堆的性质堆顶元素永远是当前数组里最大值。先把整个数组构建成大根堆。堆顶最大值和数组最后一个元素交换最大值就位。剩下前面未排序部分重新向下调整恢复成大根堆。重复交换 调整直到全部有序最终数组升序。重点升序 → 建大根堆降序 → 建小根堆。虽然这个堆是完全二叉树但是本质是还是数组这是我们将其看成了堆。为什么升序 → 建大根堆降序 → 建小根堆。堆排序是原地排序算法不开额外数组直接在原数组上完成排序。 核心循环逻辑固定不变将数组构建成堆。交换堆顶元素 和 当前堆区间最后一个元素。缩小堆的范围末尾元素已经排好不再参与堆调整。对新堆顶执行向下调整恢复堆结构重复直到有序。最核心的一步堆顶元素不是直接输出拿走而是被交换到数组尾部。这就是口诀的根源升序如果错误使用小根堆会发生什么如果你升序强行建小根堆。小根堆堆顶是当前最小值。第一次交换最小值放到数组末尾。演示图如下代码如下升序 堆排序#includeiostream using namespace std; void AdjustUp(int* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[parent] a[child]) { swap(a[parent], a[child]); child parent; parent (child - 1) / 2; } else { break; } } } void AdjustDown(int* a, int n, int parent) { int child parent * 2 1; while (child n) { if (a[child] a[child 1] child 1 n)child; if (a[child] a[parent]) { swap(a[parent], a[child]); parent child; child parent * 2 1; } else { break; } } } //升序的堆排序 void HeapSort(int* a, int n) { for (int i 1; i n; i) AdjustUp(a, i); int end n - 1; while (end 0) { swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] { 10,9,8,7,6,5,4,3,2,1 }; HeapSort(a, 10); /*SelectionSort(a, 10);*/ //InsertionSort(a, 3); //MergeSort(a, 10); /*ShellSort(a, 10);*/ /*MergeSort(a, 10);*/ /*QuickSortNonR(a, 0,9);*/ for (auto e : a) { cout e ; } return 0; }练习自己完成降序的堆排序排序的时间复杂度与空间复杂度结语希望可以帮助到你谢谢观看
排序-堆排序(Heap Sort)
目录前言堆排序思路为什么升序 → 建大根堆降序 → 建小根堆。演示图如下代码如下练习排序的时间复杂度与空间复杂度结语前言排序算法是计算机数据处理领域最基础、最核心的一类算法广泛应用于数据检索、业务统计、任务调度等场景。常见的排序算法中冒泡排序、选择排序、插入排序时间复杂度为(O(n^2))面对大规模数据时效率低下快速排序虽平均性能优异但最坏情况下时间复杂度会退化至 (O(n^2))且属于不稳定排序。堆排序作为一种基于二叉堆数据结构实现的原地排序算法凭借稳定的 (O(nlog n)) 时间复杂度、(O(1)) 的额外空间开销弥补了上述算法的短板。它借助大根堆、小根堆的特性不断选取当前区间内的极值逐步完成元素就位。在学习堆排序的过程中非常容易出现「升序建小根堆」的直觉误区。本文从堆的底层性质出发完整讲解堆排序的原理、向上调整、向下调整、建堆逻辑与排序流程结合实例剖析升序选择大根堆、降序选择小根堆的根本原因给出可运行的 C 代码实现帮助彻底吃透堆排序。其他排序快速排序排序-快速排序Quick sort基础版-CSDN博客插入排序排序—插入排序(Insertion Sort)-CSDN博客冒泡排序与选择排序排序-选择排序Selection Sort冒泡排序Bubble Sort-CSDN博客希尔排序排序-希尔排序(Shell Sort)-CSDN博客归并排序排序-归并排序Merge Sort-CSDN博客堆排序思路堆排序利用大根堆的性质堆顶元素永远是当前数组里最大值。先把整个数组构建成大根堆。堆顶最大值和数组最后一个元素交换最大值就位。剩下前面未排序部分重新向下调整恢复成大根堆。重复交换 调整直到全部有序最终数组升序。重点升序 → 建大根堆降序 → 建小根堆。虽然这个堆是完全二叉树但是本质是还是数组这是我们将其看成了堆。为什么升序 → 建大根堆降序 → 建小根堆。堆排序是原地排序算法不开额外数组直接在原数组上完成排序。 核心循环逻辑固定不变将数组构建成堆。交换堆顶元素 和 当前堆区间最后一个元素。缩小堆的范围末尾元素已经排好不再参与堆调整。对新堆顶执行向下调整恢复堆结构重复直到有序。最核心的一步堆顶元素不是直接输出拿走而是被交换到数组尾部。这就是口诀的根源升序如果错误使用小根堆会发生什么如果你升序强行建小根堆。小根堆堆顶是当前最小值。第一次交换最小值放到数组末尾。演示图如下代码如下升序 堆排序#includeiostream using namespace std; void AdjustUp(int* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[parent] a[child]) { swap(a[parent], a[child]); child parent; parent (child - 1) / 2; } else { break; } } } void AdjustDown(int* a, int n, int parent) { int child parent * 2 1; while (child n) { if (a[child] a[child 1] child 1 n)child; if (a[child] a[parent]) { swap(a[parent], a[child]); parent child; child parent * 2 1; } else { break; } } } //升序的堆排序 void HeapSort(int* a, int n) { for (int i 1; i n; i) AdjustUp(a, i); int end n - 1; while (end 0) { swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] { 10,9,8,7,6,5,4,3,2,1 }; HeapSort(a, 10); /*SelectionSort(a, 10);*/ //InsertionSort(a, 3); //MergeSort(a, 10); /*ShellSort(a, 10);*/ /*MergeSort(a, 10);*/ /*QuickSortNonR(a, 0,9);*/ for (auto e : a) { cout e ; } return 0; }练习自己完成降序的堆排序排序的时间复杂度与空间复杂度结语希望可以帮助到你谢谢观看