C语言八大排序之堆排序
目录
- 前言
- 一、堆排序的概念
- 二、堆排序的实现
- 第一步：构建堆
- 第二步：排序
- 三、完整代码
- 四、证明建堆的时间复杂度
前言
本章我们来讲解八大排序之堆排序。2022，地球Online新赛季开始了！让我们一起努力内卷吧！
一、堆排序的概念
堆排序（Heapsort）：利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。通过堆来进行选择数据，需要注意的是 排升序要建大堆，排降序建小堆。
堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：
- 空间复杂度：
- 稳定性：不稳定
二、堆排序的实现
我们先创建一个堆排序的函数：
void HeapSort(int arr[], int n);
假设我们要对下列数组来使用堆排序（升序）：
int arr[] = {70, 56, 30, 25, 15, 10, 75};
根据我们之前学到的知识，数组是可以直接看作为完全二叉树的，所以我们可以把它化为堆。此时我们就可以 "选数" （堆排序本质上是一种选择排序）。
第一步：构建堆
第一步就是要想办法把 arr 数组构建成堆（这里我们先构建成小堆）。我们介绍两种方法，分别为向上调整算法和向下调整算法：
方法1：向上调整
通过我们之前学过的 "向上调整" ，利用插入的思路来解决。首先设计下向上调整的算法：
void Swap(HPDataType* px, HPDataType* py) {
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
/* 小堆的向上调整 */
void AdjustUp(int* arr, int child) {
assert(arr);
// 首先根据公式计算算出父亲的下标
int parent = (child - 1) / 2;
// 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0）
while(child > 0) {
if(arr[child] < arr[parent]) { // 如果孩子小于父亲（不符合小堆的性质）
// 交换他们的值
Swap(&arr[child],&arr[parent]); // 传地址
// 往上走
child = parent;
parent = (child - 1) / 2;
} else { // 如果孩子大于父亲（符合小堆的性质）
// 跳出循环
break;
}
}
}
① 首先，通过公式计算出父亲的下标，公式如下：
② 其次，设计循环部分，最坏情况为调到根，如果已经符合大堆的条件则终止循环。
③ 进入循环后进行判断，如果 child ＞ parent，则交换它们的值，让父亲获得孩子的值，孩子得到父亲的值，从而让它们符合大堆的性质。
④ 交换完毕后，以便于继续判断，我们需要更新 child 和 parent 指向的元素，做到 "往上走"
此时，我们把数组里的元素依次调整即可。
方法1：
/* 升序 */
void HeapSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
AdjustUp(arr, i); // 传入数组 和 child的下标
}
}
我们不需要从 0 开始调，从 1 开始调。所以 i 的起始值设置为 1 。此时，小堆就构建好了。
方法2：向下调整
向下调整算法我们在堆那个章节也学过了，这里我们再来复习一下：
void SmallAjustDown(int* arr, int n, int parent) {
int child = parent * 2 + 1; // 默认为左孩子
while(child < n) { // 叶子内
// 选出左右孩子中小的那一个
if(child + 1 < n && arr[child + 1] < arr[child]) {
child = child + 1;
}
// 如果孩子小于父亲（不符合小堆的性质）
if(arr[child] < arr[parent]) {
// 交换它们的值
Swap(&arr[child], &arr[parent]);
// 往下走
parent = child;
child = parent * 2 + 1;
} else { // 如果孩子大于父亲（符合小堆的性质）
// 跳出循环
break;
}
}
}
① 因为要考虑左孩子还是右孩子，我们可以定义两个变量，分别记录左孩子和有孩子。但是我们这里可以用更好的方法，只需要定义一个孩子即可。具体实现方法如下：首先创建 child，我们先默认它是左孩子，利用传进来的 parent 根据公式计算出 child 的大小：
因为我们暂且默认为左孩子，我们随后进入循环后要进行检查，看看是左孩子大还是右孩子大，这里我们只需要根据数组的性质，将 child + 1 即可得到右孩子的下标，从而方便我们进行比较。比较完毕后将 child 重新赋值，拿个孩子小就将 child 给谁。
② 一共有两个结束条件（出口），第一个结束条件是父亲小于孩子就停止，第二个结束条件是chi调整到叶子。所以，循环体判断部分根据我们分析的结束条件，如果调整到叶子就结束，我们接受了 n，也就是数组的大小，只要 child 超过数组的大小（child > n） 就结束，这是第一个出口。
③ 进入循环后，对比左孩子和右孩子哪一个更小，child 就交付给谁。这里还要注意的是，要防止孩子不存在的情况，如果 child + 1 比 n 大，就说明孩子不存在。所以我们再写 if 判断条件的时候就要注意了，我们加一个 child + 1 < n 的条件限制一下：
if(child + 1 < n && arr[child + 1] < arr[child]) {...}
④ 确认好较小的孩子后，我们就可以开始比较孩子和父亲的大小了。如果孩子小于父亲，就不符合小堆的性质，我们就要交换它们的值。这里我们直接调用我们刚才写的 Swap 接口即可，这就是为什么在写向上调整的时候要我们单独把交换部分的代码写成函数的原因。
⑤ 交换完毕后，他们的值已经互相交换好了，这时我们要改变 parent 和 child 的指向，让它们往下走，parent = child ，child 再次根据公式算出新的 child 即可。
⑥ 设计下 if 的 else 部分，如果数组的 child 的值大于 parent 的值，说明符合小堆的性质了， break 跳出循环即可，这是第二个出口。
向下调整算法的前提：左右子树必须都是小堆
如果左子树和右子树不是小堆，怎么办？
可以用递归解决，但是我们能用循环就用循环来解决：
叶子所在的子树是不需要调的。所以，我们从倒着走的第一个非叶子结点的子树开始调。
（所以我们先调整30）
为了能够演示得更明显，我们再给数组再加点数据，假设我们需要对以下数组排序：
这里，我们找到了15。
…… 下标不断地 - - 后：
由于，从倒着走的第一个非叶子结点的子树开始调，即，最后一个节点的父亲。
我们已知最后一个节点的下标为：
那么，我们可以通过公式计算出他父亲的下标：
方法2：
/* 升序 */
void HeapSort(int arr[], int n) {
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(arr, n, i);
}
}
这么写或许可以看得更明白：
/* 升序 */
void HeapSort(int arr[], int sz) {
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0) {
AdjustDown(arr, sz, father);
father--;
}
}
测试堆是否创建好了：
我们这里选择使用方法2。此外，我们刚才实现的是小堆。
#include <stdio.h>
/* 交换函数 */
void Swap(int* px, int* py) {
int tmp = *px;
*px = *py;
*py = tmp;
}
/* 小堆下调 */
void AdjustDown(int arr[], int sz, int father_idx) {
int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
while (child_idx < sz) { // 最坏情況：调到叶子（child >= 数组范围时必然已经调到叶子）
if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子小
child_idx = child_idx + 1; // 让其代表右孩子
}
if (arr[child_idx] < arr[father_idx]) { // 如果孩子的值小于父亲的值（大符合小堆的性質）
Swap(&arr[child_idx], &arr[father_idx]); // 交换它们的值
/* 往下走 */
father_idx = child_idx; // 更新下标
child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲
} else { // 如果孩子的值大于父亲的值（符合小堆的性质）
break; // 终止循环
}
}
}
/* 升序 */
void HeapSort(int arr[], int sz) {
/* 创建大堆，选出最大的数 O(N) */
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0) {
AdjustDown(arr, sz, father);
father--;
}
}
void HeapPrint(int arr[], int sz) {
for (int i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void)
{
int arr[] = {70, 56, 30, 25, 15, 10, 75, 33, 50, 69};
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
HeapPrint(arr, sz);
return 0;
}
运行结果：10 15 30 25 56 70 75 33 50 69
第二步：排序
刚才介绍了两种方法来构建堆，现在堆已经构建完毕了，我们可以开始设计排序部分的算法了。
如果排升序，建小堆……
① 选出最小的数，放到第一个位置，这很简单，直接取顶部就可以得到最小的数。
② 但问题来了，如何选出次小的数呢？
从 15 开始，剩下的元素看作一个堆。但是这之前建立好的堆关系全部乱了！你还得重新建堆，才能选出次小的数。建堆的时间复杂度为 ，需要不断地建堆
则用小堆的时间复杂度就是
，这太离谱了！搞了一大圈结果居然是
，还不如直接遍历选出来的方便呢。
建小堆来排升序是完全可以的，但是效率太低！完全没有体现出你用堆的优势！
解决方法：使用大堆来排升序！
我们刚才已经实现好小堆了，根据上一节学到的知识，小堆要变成大堆，直接把刚才的代码的 "<" 改成 ">" 即可：
#include <stdio.h>
/* 交换函数 */
void Swap(int* px, int* py) {
int tmp = *px;
*px = *py;
*py = tmp;
}
/* 大堆下调 */
void AdjustDown(int arr[], int sz, int father_idx) {
int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
while (child_idx < sz) { // 最坏情況：调到叶子（child >= 数组范围时必然已经调到叶子）
if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子大
child_idx = child_idx + 1; // 让其代表右孩子
}
if (arr[child_idx] > arr[father_idx]) { // 如果孩子的值大于父亲的值（不符合大堆的性質）
Swap(&arr[child_idx], &arr[father_idx]); // 交换它们的值
/* 往下走 */
father_idx = child_idx; // 更新下标
child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲
} else { // 如果孩子的值小于父亲的值（符合大堆的性质）
break; // 终止循环
}
}
}
/* 升序 */
void HeapSort(int arr[], int sz) {
/* 创建大堆，选出最大的数 O(N) */
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0) {
AdjustDown(arr, sz, father);
father--;
}
}
void PrintArray(int arr[], int sz) {
for (int i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void)
{
int arr[] = {70, 56, 30, 25, 15, 10, 75, 33, 50, 69};
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
PrintArray(arr, sz);
return 0;
}
运行结果：75 69 70 50 56 10 30 33 25 15
现在改成了大堆，我们要排升序，我们可以让堆顶数和最后的数进行交换：
这并不会带来堆结构的破坏！我们把75不看作堆的一部分即可。再进行向下调整，就可以找到次小的数了。此时时间复杂度为
步骤总结：
① 建大堆，选出最大的数。
② 最大的数跟最后一个数交换。
③ 如何选出次大的数呢？把最后一个数不看作堆里面，进行向下调整。
代码实现（用 while）：
/* 堆排序 - 升序 */
void HeapSort(int arr[], int sz) {
/* 创建大堆，选出最大的数 O(N) */
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0) {
AdjustDown(arr, sz, father);
father--;
}
/* 依次选数，调堆 O(N * logN) */
int end = sz - 1;
while (end > 0) {
Swap(&arr[0], &arr[end]); // 最大的数跟最后一个数交换
AdjustDown(arr, end, 0); // 调堆，选出次大的数
end--;
}
}
代码实现（用 for）：
void HeapSort(int arr[], int sz) {
/* 建堆 */
for (int father = (sz - 1 - 1) / 2; father >= 0; father--) {
AdjustDown(arr, sz, father);
}
/* 排序 */
for (int end = sz - 1; end > 0; end--) {
Swap(&arr[0], &arr[end]); // 最大的数跟最后一个数交换
AdjustDown(arr, end, 0); // 调堆，选出次大的数
}
}
三、完整代码
（排升序要建大堆，排降序建小堆）
升序：使用大堆
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Swap(int* pa, int* pb) {
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void AdjustDown(int arr[], int sz, int father) {
int child = father * 2 + 1;
while (child < sz) {
if (child + 1 < sz && arr[child + 1] > arr[child]) {
child += 1;
}
if (arr[child] > arr[father]) {
Swap(&arr[child], &arr[father]);
father = child;
child = father * 2 + 1;
}
else {
break;
}
}
}
/* 堆排序 - 升序 */
void HeapSort(int arr[], int sz) {
/* 创建大堆，选出最大的数 O(N) */
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0) {
AdjustDown(arr, sz, father);
father--;
}
/* 依次选数，调堆 O(N * logN) */
int end = sz - 1;
while (end > 0) {
Swap(&arr[0], &arr[end]); // 最大的数跟最后一个数交换
AdjustDown(arr, end, 0); // 调堆，选出次大的数
end--;
}
}
void HeapPrint(int arr[], int sz) {
int i = 0;
for (i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void)
{
int arr[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前: ");
HeapPrint(arr, sz);
HeapSort(arr, sz);
printf("排序后: ");
HeapPrint(arr, sz);
return 0;
}
运行结果：
如果要排降序呢？使用小堆即可！
降序：使用小堆
#include <stdio.h>
/* 交换函数 */
void Swap(int* px, int* py) {
int tmp = *px;
*px = *py;
*py = tmp;
}
/* 小堆下调 */
void AdjustDown(int arr[], int sz, int father_idx) {
int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
while (child_idx < sz) { // 最坏情況：调到叶子（child >= 数组范围时必然已经调到叶子）
if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子小
child_idx = child_idx + 1; // 让其代表右孩子
}
if (arr[child_idx] < arr[father_idx]) { // 如果孩子的值小于父亲的值（不符合小堆的性質）
Swap(&arr[child_idx], &arr[father_idx]); // 交换它们的值
/* 往下走 */
father_idx = child_idx; // 更新下标
child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲
}
else { // 如果孩子的值大于父亲的值（符合小堆的性质）
break; // 终止循环
}
}
}
/* 堆排序 - 降序 */
void HeapSort(int arr[], int sz) {
/* 创建大堆，选出最大的数 O(N) */
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0) {
AdjustDown(arr, sz, father);
father--;
}
/* 依次选数，调堆 O(N * logN) */
int end = sz - 1;
while (end > 0) {
Swap(&arr[0], &arr[end]); // 最大的数跟最后一个数交换
AdjustDown(arr, end, 0); // 调堆，选出次小的数
end--;
}
}
void PrintArray(int arr[], int sz) {
for (int i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void)
{
int arr[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前: ");
PrintArray(arr, sz);
HeapSort(arr, sz);
printf("排序后: ");
PrintArray(arr, sz);
return 0;
}
运行结果：
四、证明建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树。此处为了简化，将采用满二叉树来证明。（时间复杂度本来看的就是近似值，所以多几个节点不会影响最终结果）：
假设树的高度为：
第 层：
个节点，需要向下移动
层
第层：
个节点，需要向下移动
层
第 层：
个节点，需要向下移动
层
第层：
个节点，需要向下移动
层
……
第 层：
个节点，需要向下移动
层
则需要移动节点总的移动步数为：
①
②
② - ① 错位相减：
因此，建堆的时间复杂度为
参考资料：
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
笔者：王亦优
更新： 2021.11.26
勘误： 无
声明： 由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！
本篇完。
到此这篇关于C语言八大排序之堆排序的文章就介绍到这了,更多相关C语言 堆排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C语言实现堆排序的简单实例
本文通过一个C语言实现堆排序的简单实例,帮助大家抛开复杂的概念,更好的理解堆排序. 实例代码如下: void FindMaxInHeap(int arr[], const int size) { for (int j = size - 1; j > 0; --j) { int parent = j / 2; int child = j; if (j < size - 1 && arr[j] < arr[j+1]) { ++child; } if (arr[child] &
-
C语言数据结构之堆排序源代码
本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科: 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高了排序效率,其效率为O(n*logn). 2. 源代码 堆排序中有两个核心的操作,一个是创建大顶堆(或者小顶堆,这里用的是大顶堆),再一个就是对堆进行调整.这里需要注意的是,并没有真
-
C语言 数据结构堆排序顺序存储（升序）
堆排序顺序存储(升序) 一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! 二:首先堆是一棵全完二叉树: a:构建一个堆分为两步:⑴创建一棵完全二叉树 ⑵调整为一个堆 (标注:大根堆为升序,小根堆为降序) b:算法描述:①创建一棵完全二叉树 ②while(有双亲){ A:调整为大根堆: B:交换根和叶子结点: C:砍掉叶子结点: } c:时间复杂度为 O(nlogn) ,空间复杂度为 O(1), 是不稳定排序! 代码实现: /*堆排序思想:[完全二叉树的定义:前
-
C语言实现基于最大堆和最小堆的堆排序算法示例
堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其
-
C语言对堆排序一个算法思路和实现代码
算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的
-
C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)
目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第
-
C语言八大排序之堆排序
目录 前言 一.堆排序的概念 二.堆排序的实现 第一步:构建堆 第二步:排序 三.完整代码 四.证明建堆的时间复杂度 前言 本章我们来讲解八大排序之堆排序.2022,地球Online新赛季开始了!让我们一起努力内卷吧! 一.堆排序的概念 堆排序(Heapsort):利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.通过堆来进行选择数据,需要注意的是 排升序要建大堆,排降序建小堆. 堆排序使用堆来选数,效率就高了很多. 时间复杂度: 空间复杂度: 稳定性:不稳定 二.堆排序的实
-
必须知道的C语言八大排序算法(收藏)
概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到
-
C语言 八大排序算法的过程图解及实现代码
目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关
-
C语言 八大排序算法的过程图解及实现代码
目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 代码实现 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具
-
C/C++语言八大排序算法之桶排序全过程示例详解
基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕. 首先我们要求出一个数组的最大数然后求出他的最大位数 //求最大位数的函数 int getmaxweisu(int* a,int len)// { int max = a[0]; for (int i = 0; i < len; i++) { if (max < a[i]) { max = a[i]; } } int count = 1; while (max/10) { count++
-
深入学习C语言中常见的八大排序
目录 冒泡排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.冒泡排序的优化 6.复杂度分析 插入排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.复杂度分析 希尔排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.复杂度分析 堆排序 1.算法描述 2.动图展示 3.图解展示 4.堆的一些基本性质 5.堆的构造 6.代码实现 7.复杂度分析 选择排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.复杂度 快速排序 1.算法简介 2.动图展
-
C语言排序之 堆排序
目录 前言: 完全二叉树在数组中下标换算公式 代码工作流程 整体流程 重建堆函数流程 大小顶堆使用场景 时间复杂度 代码 前言: 堆是具有以下性质的完全二叉树 每个节点大于或等于其左右子节点,此时称为大顶(根)堆 每个节点小于或等于其左右子节点,此时称为小顶(根)堆 完全二叉树在数组中下标换算公式 假设堆根节点从1开始编号(从1开始方便计算,0下标空着)下面以编号为i的非根节点为例,计算其关联节点的下标公式为:其父节点:i/2其左孩子:2i其右孩子:2i+1 注:把这个完全二叉树按层序遍历放入
-
python八大排序算法速度实例对比
这篇文章并不是介绍排序算法原理的,纯粹是想比较一下各种排序算法在真实场景下的运行速度. 算法由 Python 实现,可能会和其他语言有些区别,仅当参考就好. 测试的数据是自动生成的,以数组形式保存到文件中,保证数据源的一致性. 排序算法 直接插入排序 时间复杂度:O(n²) 空间复杂度:O(1) 稳定性:稳定 def insert_sort(array): for i in range(len(array)): for j in range(i): if array[i] < array[j]:
-
python实现八大排序算法（2）
本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序.堆排序.归并排序.基数排序 5.快速排序 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的. 算法思想: 已知一组无序数据a[1].a[2].--a[n],需将其按升序排列.首先任取数据a[x]作为基准.比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数
-
python实现八大排序算法（1）
排序 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问外存,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的过程. 看图使理解更清晰深刻: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序