|
C语言的魔法书：揭秘stdio.h
如何用<ctype.h>判断和转换字符类型
01
本节重点
C语言堆排序-数组的应用
堆排序是什么？
堆排序是一种基于堆这种数据结构的排序算法。堆是一种特殊的二叉树，它的每个节点都满足以下性质：
- 大顶堆：每个节点的值都大于或等于其子节点的值
- 小顶堆：每个节点的值都小于或等于其子节点的值
这样的性质保证了堆的根节点（堆顶）是整个堆中的最大值或最小值。因此，堆排序就是利用这个特点，不断地把堆顶元素和堆尾元素交换，然后调整堆的结构，直到堆中只剩下一个元素为止。
堆排序的原理
堆排序的原理可以分为两个步骤：
- 建堆：把一个无序的数组转化为一个堆
- 排序：把堆中的元素按照大小顺序输出
建堆：
建堆的过程是从数组的最后一个非叶子节点开始，依次向上调整每个节点，使其满足堆的性质。这个过程可以用一个循环来实现，如下：
// 假设数组a的长度为n，下标从0开始void build_heap(int a[], int n) { // 从最后一个非叶子节点开始，向上调整 for (int i = n / 2 - 1; i >= 0; i--) { // 调用shift_down函数，使以i为根的子树满足堆的性质 shift_down(a, i, n); }}
排序：排序的过程是不断地把堆顶元素和堆尾元素交换，然后缩小堆的大小，再调整堆的结构，直到堆中只剩下一个元素为止。这个过程也可以用一个循环来实现，如下：
// 假设数组a的长度为n，下标从0开始void heap_sort(int a[], int n) { // 先建堆 build_heap(a, n); // 循环n-1次，每次把堆顶元素和堆尾元素交换，然后缩小堆的大小，再调整堆的结构 for (int i = n - 1; i > 0; i--) { // 交换堆顶元素和堆尾元素 swap(a, 0, i); // 缩小堆的大小 n--; // 调用shift_down函数，使以0为根的子树满足堆的性质 shift_down(a, 0, n); }}
shift_down函数
shift_down函数的作用是调整以某个节点为根的子树，使其满足堆的性质。具体的做法是比较该节点和其左右子节点的值，如果该节点的值不满足堆的性质，就和其较大（或较小）的子节点交换，然后递归地调整交换后的子节点为根的子树，直到该节点的值满足堆的性质或者没有子节点为止。这个过程可以用一个递归函数来实现，如下：
// 假设数组a的长度为n，下标从0开始，i是要调整的节点的下标void shift_down(int a[], int i, int n) { // 计算左右子节点的下标 int left = 2 * i + 1; int right = 2 * i + 2; // 如果左子节点存在，且左子节点的值大于父节点的值（大顶堆的情况） if (left < n && a[left] > a) { // 交换左子节点和父节点的值 swap(a, left, i); // 递归地调整左子节点为根的子树 shift_down(a, left, n); } // 如果右子节点存在，且右子节点的值大于父节点的值（大顶堆的情况） if (right < n && a[right] > a) { // 交换右子节点和父节点的值 swap(a, right, i); // 递归地调整右子节点为根的子树 shift_down(a, right, n); }}
swap函数
swap函数的作用是交换数组中两个元素的值。这个函数可以用指针来实现，如下：
// 假设数组a的长度为n，下标从0开始，i和j是要交换的元素的下标void swap(int a[], int i, int j){ // 定义两个指针，分别指向要交换的元素 int *p = &a; int *q = &a[j]; // 定义一个临时变量，用于存储其中一个元素的值 int temp; // 把p指向的元素的值赋给temp temp = *p; // 把q指向的元素的值赋给p指向的元素 *p = *q; // 把temp的值赋给q指向的元素 *q = temp;}
堆排序的特点
堆排序的特点有以下几点：
- 堆排序是一种原地排序算法，即不需要额外的空间来存储数据，只需要在原数组上进行操作即可。
- 堆排序是一种不稳定排序算法，即可能会改变相同元素的相对顺序。例如，如果数组中有两个相同的元素，它们可能会在排序过程中被交换，导致它们的顺序发生变化。
- 堆排序的时间复杂度为
O(nlogn)
，即无论数组是有序还是无序，堆排序都需要
O(nlogn)
的时间来完成排序。这是因为建堆的过程需要
O(n)
的时间，而每次交换和调整堆的过程需要
O(logn)
的时间，共需要进行
n−1
次交换和调整，所以总的时间复杂度为
O(nlogn)
。 - 堆排序的空间复杂度为
O(1)
，即只需要常数个额外的空间来存储临时变量，不需要额外的数组或其他数据结构来辅助排序。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
