资源描述
一、实验目的熟练掌握选择排序等算法的程序实现。二、实验内容1、实现简单选择排序算法编写一个程序,实现简单选择排序算法并用相关数据进行测试2、实现堆排序算法编写一个程序,实现堆排序算法并用相关数据进行测试。程序源代码与运行结果1.#include#define MAXSIZE 10typedef int KeyType ;typedef structKeyType key;RedType;typedef structRedType rMAXSIZE+1; int length; Sqlist;int Selectminkey(Sqlist L,int i) int min=L.ri.key;int k=i;for(int j=i;jL.length;j+) if(L.rj.key=min) min=L.rj.key; k=j;return k;void Selectqsort(Sqlist &L)int j,t;for(int i=0;iL.length;i+) j=Selectminkey(L,i); if(i!=j) t=L.ri.key; L.ri.key=L.rj.key; L.rj.key=t;int main()Sqlist l;l.length=MAXSIZE;for(int i=0;il.length;i+) scanf(%d,&l.ri.key);Selectqsort(l);for(int i=0;il.length;i+)printf(%d ,l.ri.key);运行截图:I i i xj二匸卞卫笙匸ad1 34 56 2 67 78 45 65 89 00 1 2 34 45 56 65 67 78 89Process exited after 19. 78 seconds wit 请按任盍键继续 2.#include #define MAXSIZE 10 typedef int KeyType ; typedef structKeyType key; RedType; typedef struct RedType rMAXSIZE+1;int length;HeapType;void HeapAdjust(HeapType &H,int s,int m)RedType rc=H.rs;int j,i,t;for(j=2*s;j=m;j*=2)if(jm&H.rj.key=H.rj.key) break; H.rs=H.rj;s=j;H.rs=rc;void HeapSort(HeapType &H)int i,j,t;for(i=H.length/2;i0;-i)HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)t=H.r1.key;H.r1.key=H.ri.key;H.ri.key=t;HeapAdjust(H,1,i-1);int main()HeapType H;H.length=0;for(int i=1;iMAXSIZE+1;i+)scanf(%d,&H.ri.key);H.length+;HeapSort(H);for(int i=1;iMAXSIZE+1;i+)printf(%d ,H.ri.key);运行截图:1 . 谡隔结构头麵头掘九匕亡灶3 2 1 45 6 7 9 0 23 560 1 2 3 6 7 9 23 45 56Process exited 邑ftm工 15.74 second 诸按任盍键继续-三、小结(不少于 100 字)这次试验掌握了简单选择排序和堆排序两种方式;其中堆排序比较抽象难懂一些,课后 还需要多多领会。至此,我们学过了简单排序,冒泡排序法,交换排序,简单选择排序,堆 排序,其中对排序和快速排序的时间复杂度最低,而堆排序所用的辅助空间是最少的。
展开阅读全文