广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言八大排序之堆排序
  • 675

0
分享到

C语言八大排序之堆排序

2024-04-02 19:04:59 675人浏览 安东尼
摘要

目录前言一、堆排序的概念二、堆排序的实现第一步：构建堆第二步：排序三、完整代码四、证明建堆的时间复杂度 前言 本章我们来讲解八大排序之堆排序。2022，地球Online新赛季开始了！

前言

本章我们来讲解八大排序之堆排序。2022，地球Online新赛季开始了！让我们一起努力内卷吧！

一、堆排序的概念

? 堆排序（Heapsort）：利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。通过堆来进行选择数据，需要注意的是 排升序要建大堆，排降序建小堆。

堆排序使用堆来选数，效率就高了很多。

  • 时间复杂度：{\color{Red} O}({\color{Blue} N}*log{\color{Blue} N})
  • 空间复杂度：{\color{Red} O}(1)
  • 稳定性：不稳定

二、堆排序的实现

我们先创建一个堆排序的函数：


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。

…… 下标不断地 - - 后：

由于，从倒着走的第一个非叶子结点的子树开始调，即，最后一个节点的父亲。

我们已知最后一个节点的下标为：  n-1

那么，我们可以通过公式计算出他父亲的下标： parent = \frac{child -1}{2} \rightarrow \frac{\, \, \, [\, \, (n-1)-1\, \, ]\, \, \, }{2}

? 方法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) {
	
	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 开始，剩下的元素看作一个堆。但是这之前建立好的堆关系全部乱了！你还得重新建堆，才能选出次小的数。建堆的时间复杂度为 {\color{Red} O}({\color{Blue} N})，需要不断地建堆 N \, \, N-1 \, \, N-2 \, \, N-4 ...则用小堆的时间复杂度就是 {\color{Red} O}({\color{Blue} N }*{\color{Blue} N})，这太离谱了！搞了一大圈结果居然是N*N，还不如直接遍历选出来的方便呢。

建小堆来排升序是完全可以的，但是效率太低！完全没有体现出你用堆的优势！

⚡ 解决方法：使用大堆来排升序！

? 我们刚才已经实现好小堆了，根据上一节学到的知识，小堆要变成大堆，直接把刚才的代码的 "<" 改成 ">" 即可： 


#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) {
	
	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不看作堆的一部分即可。再进行向下调整，就可以找到次小的数了。此时时间复杂度为 

{\color{Red} O}({\color{Blue} N} * log{\color{Blue} N})

? 步骤总结：

① 建大堆，选出最大的数。

② 最大的数跟最后一个数交换。

③ 如何选出次大的数呢？把最后一个数不看作堆里面，进行向下调整。

? 代码实现（用 while）：



void HeapSort(int arr[], int sz) {
	
	int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
	while (father >= 0) {
		AdjustDown(arr, sz, father);
		father--;
	}
 
	
	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) {
	
	int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
	while (father >= 0) {
		AdjustDown(arr, sz, father);
		father--;
	}
 
	
	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) {
	
	int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
	while (father >= 0) {
		AdjustDown(arr, sz, father);
		father--;
	}
 
	
	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;
}

? 运行结果：

四、证明建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树。此处为了简化，将采用满二叉树来证明。（时间复杂度本来看的就是近似值，所以多几个节点不会影响最终结果）：

假设树的高度为h：

第 1层：2^0个节点，需要向下移动h-1层

第2层：2^1个节点，需要向下移动h-2层

第 3层：2^2个节点，需要向下移动h-3层

第4层：2^3个节点，需要向下移动h-4 层

……

第 h - 1 层：2^{h-2} 个节点，需要向下移动1 层

则需要移动节点总的移动步数为：

T(n) = 2^0 * (h-1) + 2^1 *(h-2) + 2^2 * (h-3) + 2^3 * (h-4) + ... + 2^{h-3} * 2 + 2^{h-2} * 1

   ①

2T(n) = 2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+2^4*(h-4)+...+2^{h-2}*2+2^{h-1}*1

   ②

② - ① 错位相减：

T(n) = 1-h+2^1+2^2+2^3+2^4+...+2^{h-2}+2^{h-1}

T(n) = 2^0+2^1+2^2+2^3+2^4+...+2^{h-2} + 2^{h-1}-h

T(n) = 2^h - 1 - h

n = 2^h-1\, \, \, \, \,\, \, \, \, \, \, h = log_2(n+1)

T(n) = n-log_2(n+1) \approx n

因此，建堆的时间复杂度为 {\color{Red} O}({\color{Blue} N})  

参考资料：

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

? 笔者：王亦优

? 更新： 2021.11.26

❌ 勘误： 无

? 声明： 由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！

本篇完。

到此这篇关于C语言八大排序之堆排序的文章就介绍到这了,更多相关C语言 堆排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言八大排序之堆排序

本文链接: https://www.lsjlt.com/news/140517.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言八大排序之堆排序
    目录前言一、堆排序的概念二、堆排序的实现第一步：构建堆第二步：排序三、完整代码四、证明建堆的时间复杂度 前言 本章我们来讲解八大排序之堆排序。2022，地球Online新赛季开始了！...
    99+
    2022-11-13
  • C语言排序之 堆排序
    目录前言：完全二叉树在数组中下标换算公式代码工作流程整体流程重建堆函数流程大小顶堆使用场景时间复杂度代码前言： 堆是具有以下性质的完全二叉树 每个节点大于或等于其左右子节点，此时称为...
    99+
    2022-11-13
  • 八大排序（三）堆排序，计数排序，归并排序
    一、堆排序 什么是堆排序：堆排序（Heap Sort）就是对直接选择排序的一种改进。此话怎讲呢？直接选择排序在待排序的n个数中进行n-1次比较选出最大或者最小的，但是在选出最大或者最小的数后，并没有对原来的序列进行改变，这使得下一次选数时还...
    99+
    2023-10-21
    算法 数据结构
  • C语言排序算法之选择排序(直接选择排序,堆排序)
    目录前言一、直接选择排序1.1 算法思想1.2 代码实现1.3 直接选择排序的特征总结二、堆排序2.1 什么是堆？2.2 判断是否是堆2.3 向下调整算...
    99+
    2022-11-13
  • C/C++语言八大排序算法之桶排序全过程示例详解
    基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶，先个位装桶然后出桶，直到最高位入桶出桶完毕。 首先我们要求出一个数组的最大数然后求出他的最大位数  //...
    99+
    2022-11-12
  • C语言数据结构之堆排序详解
    目录1.堆的概念及结构2.堆的实现2.1 堆的向下调整算法2.2 堆的向上调整算法2.3 建堆（数组）2.4 堆排序2.5 堆排序的时间复杂度1.堆的概念及结构 如果有一个关键码的集...
    99+
    2022-11-13
  • C语言中堆排序怎么用
    小编给大家分享一下C语言中堆排序怎么用，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！一、堆排序的概念 堆排序（Heapsort）：利用堆积树（堆）这种数据结构所设...
    99+
    2023-06-29
  • 【数据结构--八大排序】之快速排序
    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 ἴ...
    99+
    2023-10-26
    数据结构
  • JAVA十大排序算法之堆排序详解
    目录堆排序知识补充二叉树满二叉树完全二叉树二叉堆代码实现时间复杂度算法稳定性思考总结堆排序 这里的堆并不是JVM中堆栈的堆，而是一种特殊的二叉树，通常也叫作二叉堆。它具有以下特点： ...
    99+
    2022-11-12
  • Java十大排序算法之堆排序刨析
    二叉堆是完全二叉树或者是近似完全二叉树。 二叉堆满足二个特性︰ 1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。 2．每个结点的左子树和右子树都是一个二叉堆（都是最...
    99+
    2022-11-12
  • 深入学习C语言中常见的八大排序
    目录冒泡排序1.算法描述2.动图展示3.图解展示4.代码实现5.冒泡排序的优化6.复杂度分析插入排序1.算法描述2.动图展示3.图解展示4.代码实现5.复杂度分析希尔排序1.算法描述...
    99+
    2022-11-12
  • C语言常见排序算法之交换排序(冒泡排序,快速排序)
    目录前言1.交换排序——冒泡排序1.1 算法思想1.2 动图演示1.3 冒泡最好的情况 2. 交换排序——快速排序...
    99+
    2022-11-13
  • C语言数据结构之堆、堆排序的分析及实现
    目录 1.堆的概念结构及分类1.2堆的分类1.2.1 大堆1.2.2 小堆2. 堆的主要接口3.堆的实现3.1 堆的初始化 HeapInit3.2 堆的销毁 HeapDes...
    99+
    2022-11-13
  • C语言堆怎么实现和堆排序是什么
    这篇文章主要介绍了C语言堆怎么实现和堆排序是什么的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C语言堆怎么实现和堆排序是什么文章都会有所收获，下面我们一起来看看吧。一、本章重点堆的介绍堆的接口实现堆排序二、堆2...
    99+
    2023-06-29
  • C语言常见排序算法之插入排序(直接插入排序,希尔排序)
    目录前言一、直接插入排序1.1 基本思想1.2 算法思想1.3 程序实现1.4 直接插入排序的总结二、希尔排序2.1 算法思想2.2 程序实现2.3 希尔排序的特征总结前言...
    99+
    2022-11-13
  • C语言数据结构之堆排序的优化算法
    目录1.堆排序优化算法1.1建堆的时间复杂度1.1.1 向下调整建堆：O(N)1.1.2 向上调整建堆：O(N*logN)1.2堆排序的复杂度1.2.1原堆排序的时间复杂度...
    99+
    2022-11-13
  • 图解Java排序算法之堆排序
    目录预备知识堆排序堆堆排序基本思想及步骤再简单总结下堆排序的基本思路：总结预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均...
    99+
    2022-11-12
  • Python排序算法之堆排序算法
    目录1. 树满二叉树的特性：什么是完全二叉树？完全二叉树的专业概念：2. 二叉堆2.1 二叉堆的抽象数据结构2.2 API 实现3. 堆排序4. 后记本文从树数据结构说到二叉堆数据结...
    99+
    2023-01-07
    python堆排序算法实现 堆排序算法以及python实现 python 堆排序算法
  • c语言排序之归并排序(递归和非递归)
    目录递归代码流程非递归代码流程两者比较时间复杂度代码（递归）代码（非递归）递归代码流程 归并就是把两个或多个序列合并，这里只介绍二路归并，就是不断的把序列分为2组，直到每个组有一个元...
    99+
    2022-11-13
  • Java基础之八大排序算法
    目录前言一、直接插入排序二、希尔排序三、简单选择排序四、堆排序五、冒泡排序六、快速排序七、归并排序八、基数排序(桶排序)前言 关系 复杂度 一、直接插入排序 基本思想： 将新的数...
    99+
    2022-11-12
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作