河南工业大学实验报告——查找和排序(排序)——张伟龙

《河南工业大学实验报告——查找和排序(排序)——张伟龙》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、河南工业大学实验报告课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203姓名张伟龙学号201216010313指导老师范艳峰日期2013.6.5批改日期成绩一实验目的掌握希尔排序、快速排序、堆排序的算法实现。二实验内容及要求实验内容：1．实现希尔排序。2．实现快速排序。3.实现堆排序。（三选一）实验要求：1.根据所选题目，用C语言编写程序源代码。2.源程序必须编译调试成功，独立完成。三实验过程及运行结果选择第三题：SourceCode：#include

2、tream>#includeusingnamespacestd;voidHeapAdjust(int*a,inti,intsize)//调整堆{intlchild=2*i;//i的左孩子节点序号intrchild=2*i+1;//i的右孩子节点序号intmax=i;//临时变量if(i<=size/2)//如果i是叶节点就不用进行调整{if(lchild<=size&&a[lchild]>a[max]){max=lchild;}if(rchild<=size&&a[rchild

3、]>a[max]){max=rchild;}if(max!=i){swap(a[i],a[max]);HeapAdjust(a,max,size);//避免调整之后以max为父节点的子树不是堆}}}voidBuildHeap(int*a,intsize)//建立堆{inti;for(i=size/2;i>=1;i--)//非叶节点最大序号值为size/2{HeapAdjust(a,i,size);}}voidHeapSort(int*a,intsize)//堆排序{inti;BuildHeap(a,

4、size);for(i=size;i>=1;i--){swap(a[1],a[i]);//交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面HeapAdjust(a,1,i-1);//重新调整堆顶节点成为大顶堆}}intmain(){inta[100];intsize;while(scanf("%d",&size)==1,size){inti;for(i=1;i<=size;i++)cin>>a[i];HeapSort(a,size);for(i=1;i<=size;i++)cout<

5、[i]<<"";cout<