IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 堆排序的理解 -> 正文阅读

[数据结构与算法]堆排序的理解

堆排序的关键是对最大堆的理解(或最小堆)

最大堆形成动画

以下面数组为例

int arr[10] = { 1,23,4,5,67,563,3543,4234,66,44 };

首先我们要知道父节点n的两个字节点为2*n+1和2*n+2

在第一次得到最大堆之后

我们把a[0]与a[9]换值

可以的到a[9]是大小在数组里是第一大

所以之后我们只需要对a[0]至a[8]排序

再次形成最大堆

以此类推

下面是代码

#include <iostream>
#include <cstring>
#include<cstdio>
using namespace std;
//交换a和b的值
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void max_sort(int arr[], int start, int end) {
	int dad = start;//父节点
	int son = dad * 2 + 1;//第一个子节点
	while (son <= end) {
		//选择两个子节点中较大的那一个节点
		if (arr[son] < arr[son+1]&&son+1<=end) {
			son++;
		}
		//如果父节点比子节点小 那么交换值 并且把原来的父节点与现在的字节点比较
		if (arr[dad] < arr[son]) {
			swap(&arr[dad], &arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
		else {
			return;
		}
	}
}
void heap_sort(int arr[], int len) {
	for (int i = len / 2 - 1; i >= 0; i--) {
		max_sort(arr, i, len - 1);
	}
	//得到最大堆
	for (int i = len - 1; i > 0; i--) {
		swap(&arr[0], &arr[i]);
		max_sort(arr, 0,i - 1);
	}
	//将数组arr[0]至arr[i]中最大的数arr[0]与最后的arr[i]换位置
	//再对数组arr[0]至arr[i-1]的元素进行堆排序
}
int main() {
	int arr[10] = { 1,23,4,5,67,563,3543,4234,66,44 };//用堆排序将数字由小到大排序
	int len = sizeof(arr)/sizeof(int);//计算数组的大小;
	heap_sort(arr, len);//堆排序函数 
	for (int i = 0; i < len; i++) {//输出结果
		printf("%d ", arr[i]);
	}
	return 0;
}

  数据结构与算法 最新文章
【数据结构】二叉查找树/二叉搜索树BST(附
二叉树的前序后续中序遍历(迭代)(C++)
【贪心算法】手办合并
LeetCode 每日一题——462. 最少移动次数使
leetcode47. 全排列 II
Java二叉树
线性结构(一)
【Java版算法思想(排序)】选择&冒泡&
LeetCode系列49—字母异位词分组
NC78 反转链表
上一篇文章      下一篇文章      查看所有文章
加:2022-01-17 11:44:21  更:2022-01-17 11:46:47 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年5日历 -2022/5/24 4:38:14-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码