堆排序C++实现

清疚 2022-05-15 13:06 140阅读 0赞

// 堆排序.cpp : Defines the entry point for the console application.  
//时间复杂度为nlgn  
//建立最大堆

\#include "stdafx.h"  
\#include<iostream>  
using namespace std;  
int A\[100\];  
//  
//保持堆得性质  
//a 为待排序数组，sum是待排序元素个数 i是父元素序号  
void keep\_heapify(int \*a,int sum,int i)  
\{  
int left = 2\*i;  
int right = 2\*i+1;  
int largest = i;  
if(left<=sum&&a\[left\]>a\[i\])  
largest = left;  
if(right<=sum&&a\[right\]>a\[largest\])  
largest = right;  
if(largest!=i)  
\{  
int temp = a\[i\];  
a\[i\] = a\[largest\];  
a\[largest\] = temp;  
keep\_heapify(a,sum,largest);  
\}  
\}  
//创建大堆  
void create\_heap(int \*a,int sum)  
\{  
int i;  
for(i=sum/2;i>=1;i--)  
\{  
keep\_heapify(a,sum,i);  
\}  
\}

//堆排序  
//首先建立大堆，然后交换堆顶和堆底的元素，待排序元素总数减一  
//调用keep\_heapify()保持堆性质，直到排完  
void heap\_sort(int \*a,int sum)  
\{  
create\_heap(a,sum);  
int j;  
int num = sum;  
for(j=sum;j>=2;j--)  
\{  
num--;  
int temp = a\[1\];  
a\[1\]=a\[j\];  
a\[j\]=temp;  
keep\_heapify(a,num,1);  
\}  
\}

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int cases;  
cout<<"请输入案例个数："<<endl;  
cin>>cases;  
while(cases--)  
\{  
cout<<"请输入需要排序元素的个数："<<endl;  
int n;  
cin>>n;  
int k;  
cout<<"请输入需要排序的元素："<<endl;  
for(k=1;k<=n;k++)  
cin>>A\[k\];  
cout<<"排序前："<<endl;  
for(k=1;k<=n;k++)  
cout<<A\[k\]<<" ";  
cout<<endl;  
heap\_sort(A,n);  
cout<<"堆排序后："<<endl;  
for(k=1;k<=n;k++)  
cout<<A\[k\]<<" ";  
cout<<endl;  
\}  
system("pause");  
return 0;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关堆排序(C实现)

堆排序 **目录** 堆的概念及结构堆的实现堆排序堆排序的特点堆排接口实现 -------------------- > 堆的概念...

悠悠/ 2024年04月17日 05:54/ 0 赞/ 32 阅读

相关堆排序 C语言实现

堆排序 (Heap Sort) 是一种树形选择排序，在排序过程中，将待排序的记录Data\[1…n\]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子

古城微笑少年丶/ 2022年12月22日 13:30/ 0 赞/ 118 阅读

相关 c/c++排序算法-堆排序

文章目录基本思想算法的实现：时间复杂度空间复杂度基本思想 > 堆顶元素（即第一个元素）必为最小项（

旧城等待，/ 2022年10月02日 11:57/ 0 赞/ 130 阅读

相关堆排序C++实现

// 堆排序.cpp : Defines the entry point for the console application. //时间复杂度为nlgn //建立最

Myth丶恋晨/ 2022年06月18日 10:17/ 0 赞/ 125 阅读

相关 C语言实现堆排序算法

利用堆排序的思想将一个数组按递增的顺序进行排序，将数组的第一个位置空下（下标为0），因为会导致子节点和本身同一个结点（i和2i一致），每次堆排序在下标1的位置放上了

小灰灰/ 2022年06月03日 01:59/ 0 赞/ 174 阅读

相关堆的C语言实现——堆与堆排序（二）

堆的C语言实现——堆与堆排序（二）堆的C语言实现——堆与堆排序（二）头文件初始化函数下滤函数1（递归）

Myth丶恋晨/ 2022年05月25日 02:41/ 0 赞/ 138 阅读

相关堆排序——ANSI C实现

typedef int ElementType; / 利用中间变量的交换算法 / void Swap(ElementType a, Eleme

墨蓝/ 2022年05月18日 00:05/ 0 赞/ 158 阅读

相关堆排序C++实现

// 堆排序.cpp : Defines the entry point for the console application. //时间复杂度为nlgn //建立最

清疚/ 2022年05月15日 13:06/ 0 赞/ 141 阅读

相关堆排序C++实现

// 堆排序.cpp : Defines the entry point for the console application. //时间复杂度为nlgn //建立最

深碍√TFBOYSˉ_/ 2022年05月15日 13:06/ 0 赞/ 152 阅读

相关堆排序算法（C#实现）

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储

ゝ一世哀愁。/ 2021年11月26日 16:56/ 0 赞/ 222 阅读