您的位置:首页 > 房产 > 建筑 > 中山网站建设制作_苏州建站公司兴田德润i网址多少_最好的关键词排名优化软件_电子商务营销的概念

中山网站建设制作_苏州建站公司兴田德润i网址多少_最好的关键词排名优化软件_电子商务营销的概念

2024/12/23 15:05:09 来源:https://blog.csdn.net/B5201234/article/details/144349990  浏览:    关键词:中山网站建设制作_苏州建站公司兴田德润i网址多少_最好的关键词排名优化软件_电子商务营销的概念
中山网站建设制作_苏州建站公司兴田德润i网址多少_最好的关键词排名优化软件_电子商务营销的概念

任务描述


本关任务:实现堆排序算法,并将乱序数列变成升序。

相关知识


为了完成本关任务,你需要掌握:1.堆排序算法。

堆排序算法


堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

算法步骤:


将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;

将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

编程要求


本关的编程任务是补全右侧代码片段adjustHeap和heap_sort中Begin至End中间的代码,具体要求如下:

在adjustHeap中,实现堆的调整。
在heap_sort中,构建大顶堆,并调用adjustHeap实现堆的调整。
测试说明
平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入:
10
7 1 4 6 8 9 5 2 3 10
预期输出:
1 2 3 4 5 6 7 8 9 10

测试输入:
15
3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
预期输出:
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

测试代码 

//
//  sort_.cpp
//  Sort
//
//  Created by ljpc on 2018/4/20.
//  Copyright © 2018年 ljpc. All rights reserved.
//#include "sort_.h"void print_array(int *arr, int n)
// 打印数组
{if(n==0){printf("ERROR: Array length is ZERO\n");return;}printf("%d", arr[0]);for (int i=1; i<n; i++) {printf(" %d", arr[i]);}printf("\n");
}void adjustHeap(int *arr, int param1, int j)
// 编程实现堆的调整
{// 请在这里补充代码,完成本关任务/********** Begin *********//********** End **********/
}int* heap_sort(int *arr, int n)
//  基于adjustHeap函数编程实现堆排序
//  函数参数:无序数组arr 数组长度n
//  函数返回值:返回从小到大排序后的数组
{// 请在这里补充代码,完成本关任务/********** Begin *********//********** End **********/
}

 补充代码:

//
//  sort_.cpp
//  Sort
//
//  Created by ljpc on 2018/4/20.
//  Copyright © 2018年 ljpc. All rights reserved.
//#include "sort_.h"
typedef int ElementType;
void print_array(int *arr, int n)
// 打印数组
{if(n==0){printf("ERROR: Array length is ZERO\n");return;}printf("%d", arr[0]);for (int i=1; i<n; i++) {printf(" %d", arr[i]);}printf("\n");
}void adjustHeap(int *arr, int param1, int j)
// 编程实现堆的调整
{// 请在这里补充代码,完成本关任务/********** Begin *********/int child;ElementType Tmp;for (Tmp = arr[param1]; 2*param1+1 < j; param1 = child){child = 2*param1+1; if (child != j - 1 && arr[child + 1] > arr[child])++child;              if (Tmp < arr[child])arr[param1] = arr[child];elsebreak;}arr[param1] = Tmp;/********** End **********/
}void Swap(int* a,int* b)
{int temp=*a;*a=*b;*b=temp;
}int* heap_sort(int *arr, int n)
//  基于adjustHeap函数编程实现堆排序
//  函数参数:无序数组arr 数组长度n
//  函数返回值:返回从小到大排序后的数组
{// 请在这里补充代码,完成本关任务/********** Begin *********/int i;for (i = n / 2; i >= 0; --i)adjustHeap(arr, i, n);  for(i=n-1;i>0;--i){Swap(&arr[0],&arr[i]);       adjustHeap(arr, 0, i);}return arr;/********** End **********/
}

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com