假设基本数据为整型，输入为一串无序的整数，请用堆排序的方式对该整数串排序（增序），有重复时保留重复的数。
测试数据:[3,6,23,4,3,2,9,10,18,11]
（1）堆排序的思想，使用情况一般是什么？
（2）算法所需要的数据结构？
（3）用你习惯的语言或者伪代码实现你的算法？
①根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
②每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
（2）算法所需要的数据结构？
涉及到二叉堆的数据结构| import java.util.Arrays;
public class HeapSort { public static void main(String[] args) { int[] a={3,6,23,4,3,2,9,10,18,11}; int arrayLength=a.length; //循环建堆 for(int i=0;i<arrayLength-1;i++){ //建堆 buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } System.out.println(Arrays.toString(a)); } //对data数组从0到lastIndex建大顶堆 public static void buildMaxHeap(int[] data, int lastIndex){ //从lastIndex处节点（最后一个节点）的父节点开始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在 while(k*2+1<=lastIndex){ //k节点的左子节点的索引 int biggerIndex=2*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 if(biggerIndex<lastIndex){ //若果右子节点的值较大 if(data[biggerIndex]<data[biggerIndex+1]){ //biggerIndex总是记录较大子节点的索引 biggerIndex++; } } //如果k节点的值小于其较大的子节点的值 if(data[k]<data[biggerIndex]){ //交换他们 swap(data,k,biggerIndex); //交换后小的值会被换下来，需要将biggerIndex赋予k， //开始while循环的下一次循环，重新保证k节点（被换下来）的值仍然大于其左右子节点的值 k=biggerIndex; }else{ break; } } } } //交换 private static void swap(int[] data, int i, int j) { int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } } |
发表于 2017-07-30 21:48:19
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
堆排序多用于实现优先队列。
当排序可能终止，并且需要从已处理的数据选出最大的几个数据时，可以使用堆排序。
2.使用线性数据结构比如数组就可以实现堆排序
3.
#define LeftChild(i) (2*(i)+1) void perc_down(int a[], int i, int N) { int child; int tmp; for(tmp = a[i]; LeftChild(i) < N; i = child) { child = LeftChild(i); if(child!=N-1 && A[child+1]>A[child]) child++; if(tmp < a[child]; a[i] = a[child]; else break; } A[i] = tmp; } void headsort(int a[], int N) { int i; for(i = N/2; i >= 0; i--) perc_down(A, i, N); for(i = N-1; i > 0; i--) { swap(&A[0], &A[i]); perc_down(A, 0, i); } }