营销网站建设流程图,搭建的网站403,开网店需要多少钱?,2023年中国企业500强目录
前言
建议
简介
A.建堆#xff1a;
B.排序
一、代码实现
二、时空复杂度
A.时间复杂度
B.空间复杂度
三、稳定性
四、现实中的应用 前言
建议
1.学习算法最重要的是理解算法的每一步#xff0c;而不是记住算法。
2.建议读者学习算法的时候#xff0c;自己…目录
前言
建议
简介
A.建堆
B.排序
一、代码实现
二、时空复杂度
A.时间复杂度
B.空间复杂度
三、稳定性
四、现实中的应用 前言
建议
1.学习算法最重要的是理解算法的每一步而不是记住算法。
2.建议读者学习算法的时候自己手动一步一步地运行算法。
tips文中的对数均以2为底数 简介
堆排序是一种基于堆数据结构的排序算法。它分为两个主要步骤建堆和排序。
A.建堆
建堆的过程是将一个无序的数组构建成一个堆通常采用最大堆Max Heap的形式。最大堆是一种特殊的二叉树其中每个节点的值都大于或等于其子节点的值。下面是建堆的简单步骤
1.从最后一个非叶子节点开始 最后一个非叶子节点的索引可以通过 (n/2 - 1) 计算其中 n 是数组的长度。非叶子节点是指有子节点的节点。
2.进行堆调整Heapify 对于每个非叶子节点进行堆调整将当前节点与其子节点比较确保当前节点是最大的。如果子节点的值较大则交换节点值然后递归地调整子树。
3.逐层向上重复 重复步骤2逐层向上处理非叶子节点直到根节点。这样就确保了整个数组构成了一个最大堆。 B.排序
排序的过程是将一个无序的数据集合按照一定规则重新排列成有序的序列。以下是一般排序算法的简单过程
1.比较元素 排序算法的第一步是通过比较元素来确定它们的相对顺序。比较可以根据不同的规则进行例如升序或降序。
2.交换元素 根据比较的结果可能需要交换元素的位置以达到正确的顺序。这是排序算法中一个关键的步骤。
3.重复步骤1和2 排序算法会持续比较和交换元素直到整个数据集合中的元素都按照规则有序排列。 一、代码实现 #include stdio.h// 交换数组中两个元素的值
void swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}// 调整堆保持最大堆性质
void maxHeapify(int arr[], int n, int i) {int largest i; // 初始化最大值的索引为根节点int left 2 * i 1; // 左子节点的索引int right 2 * i 2; // 右子节点的索引// 如果左子节点比根节点大则更新最大值的索引if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点比当前最大值大则更新最大值的索引if (right n arr[right] arr[largest]) {largest right;}// 如果最大值的索引不是根节点交换它们的值并递归调整子树if (largest ! i) {swap(arr[i], arr[largest]);maxHeapify(arr, n, largest);}
}// 建立最大堆
void buildMaxHeap(int arr[], int n) {// 从最后一个非叶子节点开始逐个调整子树使其满足最大堆性质for (int i n / 2 - 1; i 0; i--) {maxHeapify(arr, n, i);}
}// 堆排序主函数
void heapSort(int arr[], int n) {// 建立最大堆buildMaxHeap(arr, n);// 从最后一个元素开始逐个将当前最大元素交换到数组末尾for (int i n - 1; i 0; i--) {swap(arr[0], arr[i]); // 将当前最大元素移动到数组末尾maxHeapify(arr, i, 0); // 调整堆保持最大堆性质}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: );printArray(arr, n);heapSort(arr, n);printf(堆排序后的数组: );printArray(arr, n);return 0;
}这段代码首先建立一个最大堆然后通过不断交换根节点和最后一个节点并调整堆的方式实现堆排序。 二、时空复杂度
A.时间复杂度 堆排序算法的时间复杂度主要由两个部分构成建堆的时间复杂度和排序的时间复杂度。
建堆时间复杂度 建堆的过程需要从最后一个非叶子节点开始对每个节点进行堆调整Heapify使得整个数组构成一个最大堆。建堆的时间复杂度是其中n是数组的长度。
排序时间复杂度 在建堆完成后堆的根节点是数组中的最大元素。将根节点与数组末尾的元素交换然后重新调整堆这样就把最大的元素放到了数组末尾。重复这个过程每次交换后堆的大小减一直到整个数组有序。由于进行n次交换和调整排序的时间复杂度也是。
因此堆排序的总时间复杂度是建堆和排序时间复杂度的和。 B.空间复杂度
堆排序的空间复杂度主要包括两个方面原地排序所需的空间和递归调用的栈空间。
原地排序 堆排序是一种原地排序算法它不需要额外的辅助数组来存储数据。排序过程中主要是通过在输入数组上进行元素交换而不需要额外的存储空间。因此原地排序的空间复杂度为 O(1)。
递归调用的栈空间 在堆排序的建堆过程中通常会使用递归调用或迭代方式来实现堆调整。递归调用会在调用栈中占用一定的空间其空间复杂度与递归深度相关。最坏情况下堆排序的递归深度为堆的高度即其中 n 是输入数组的长度。因此递归调用的空间复杂度为 。
因此原地排序和递归调用的空间开销堆排序的总体空间复杂度为 。这表明堆排序的空间需求相对较低是一个空间效率较好的排序算法。 三、稳定性
在排序过程中可能会交换相同值的元素的相对位置导致相等元素之间的原始相对顺序被打乱。具体来说在建堆和排序的过程中会涉及到元素的交换操作。如果两个相等元素的顺序在排序之前是相对的那么在排序之后它们的相对顺序可能会发生变化。由于堆排序是通过不断交换堆顶元素和数组末尾元素并调整堆的过程来实现的这种交换可能破坏相同元素的相对顺序。因此堆排序不是稳定的排序算法。 四、现实中的应用
堆排序虽然在某些方面不如一些简单的排序算法直观但在现实中仍然有一些应用场景其中它的优势得到充分发挥
优先队列 堆排序常用于实现优先队列其中最大堆或最小堆的性质使得可以高效地找到最大或最小元素。这在任务调度、事件模拟等领域有广泛应用。
堆作为数据结构的一部分 堆结构本身作为一种数据结构可以被应用于图算法中的最短路径算法如Dijkstra算法和最小生成树算法如Prim和Kruskal算法等。堆排序作为堆结构的一种附带应用用于维护和操作堆。
外部排序 在需要对大规模数据进行排序的情况下堆排序相对于其他算法的稳定的时间复杂度使得它成为外部排序算法的一种选择。外部排序涉及到将大量数据从外部存储例如硬盘加载到内存中进行排序然后再写回外部存储。
不稳定排序的需求 在某些情况下不需要保持相同值元素的相对顺序而更关注排序算法的性能此时堆排序可以是一个合适的选择。
