首页天道酬勤()

()

admin 12-02 07:54 204次浏览

00-1010在前一章中,我们已经详细介绍了排序的相关概念(学习笔记-排序简介),本文旨在详细介绍堆排序。

本文目的

Heapsort(英文:heap)是指利用堆的数据结构设计的一种排序算法。堆是一种近乎完整的二叉树结构,同时满足堆的性质:即子节点的键值或索引总是小于(或大于)其父节点。

00-1010 Heap是计算机科学中一种特殊数据结构的总称。堆是一种非线性结构。堆可以被视为一个数组或一个完整的二叉树。一般来说,堆实际上是一个由完整二叉树结构维护的一维数组。这里所用的堆一般指大顶堆或小顶堆。

大堆

每个节点的值大于或等于其左右子节点的值,称为大顶堆。如下图所示。

定堆

每个节点的值小于或等于其左右子节点的值,这称为小顶堆。如下图所示。

堆排序

构造要排序的序列成为一个大的顶堆,此时,整个序列的最大值就是堆顶的根节点。与最后一个元素交换,此时结束为最大值。然后,剩余的n-1个元素被重建成一个堆,从而可以获得n个元素的下一个最小值。在重复执行之后,可以获得有序序列。需要注意的是,大顶堆是从最后一个非叶节点开始自下而上调整的。

堆是什么

1.创建堆R [0.n-1];

2.交换头部(最大值)和尾部;

3.将堆的大小减少1(已经订购的部分不会进入下一轮);

4.重复步骤2,直到堆的大小为1。

算法原理

操作流程如下:

1.初始化堆:构造R[1.n]作为一堆;

2.将当前无序区堆的顶部元素R[1]与区间的最后一条记录进行交换,然后将新的无序区调整为新的堆。

#包含stdio.h

#定义元素类型int /*元素类型*/

int k=1;//回合记录

//打印功能

无效打印(elemType arr[],int len){ 0

int I;

for(I=0;伊琳;I){ 0

printf ('%d\t ',arr[I]);

}

printf(' \ n ');

}

//记录交换

无效交换(int* a,int* b)

{

int temp=* b;

* b=* a;

*a=温度;

}

//建一个大的顶桩

void max_heapify(int a[],int start,int end)

{

//创建父节点指示器和子节点指示器

int dad=start

int son=dad * 2 1;

//仅当子节点指标在范围内时比较。

while (son=end)

if (son 1=end a[son] a[son 1]) {

//首先比较两个子节点的大小,选择最大的一个。

儿子;

}

//如果父节点大于子节点,说明调整完成,直接跳出功能。

如果(父亲[儿子])

返回;

}else{

//否则,交换父子内容,继续子节点和孙子节点的比较。

互换(一个[爸爸],一个[儿子]);

爸爸=儿子;

儿子=爸爸* 2 1;

}

}

}

//排序

void Sort(elemType a[],int len)

{

int I;

//初始化,我从最后一个父节点开始调整

for(I=len/2-1;I=0;I-){ 0

max_heapify(a,I,len-1);

}

for(I=len-1;I 0;i -)

{

//首先将第一个元素与前一个排列好的元素交换,然后重新调整,直到排序完成。

swap(a[0],a[I]);

max_heapify(a,0,I-1);

Printf('第一个==% d===轮次排序后的结果如下:\n ',k);

打印(a,9);

k=k1;

}

}

int main(){ 0

int I;

elemType arr[9]={94,19,29,9,11,1,14,13,29 };

Printf('要排序的序列是:\ n ');

印刷(arr,9);

printf(' \ n \ n ');

排序(arr,9);

printf(' \ n \ n ');

Printf('排序结果如下:\ n ');

印刷(arr,9);

}

00-1010时间复杂度

堆排序的运行时间主要消耗在堆构建和堆重构时的重复筛选上。在堆构建的过程中,由于我们从完全二叉树的最低非叶节点开始,所以我们将其与其子节点进行比较,并根据需要进行交换。对于每个非叶节点,实际上最多有两次比较和交换,因此初始化堆的时间复杂度是O(n)。在形式排序中,第I次取堆顶记录并重建堆需要O(logi)时间(完整二叉树的一个节点到根节点的距离为log2i 1),取堆顶记录需要n-1次,因此重建堆的时间复杂度为O(nlogn)。一般来说,堆排序的时间复杂度为O(nlogn)。因为堆排序对元素记录的排序状态不敏感,所以它的最佳、最差和平均时间复杂度都是O(nlogn)。

空间复杂性

在堆中交换元素时只有一个辅助空间,与问题规模无关,空间复杂度为O(1)。

分选稳定性

在堆构建过程中,无法保证构建前后相同值的相对位置,因此堆排序不稳定。

本文初衷是分享学习笔记,部分图文来源于网络,如侵删。

C#实现一个控制台的点餐系统雷士灯具管理系统
一共多少种职业(现在有几种usb接口) ()
相关内容