(1)简单选择排序
头文件:
#defineMAXSIZE20
#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))
typedefintKeyType;
typedefintInfoType;
typedefstruct...{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct...{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
源文件:
#include"sort.h"
#include"stdio.h"
voidinit(SqList&s,intw[],intn)...{
s.length=n;
for(inti=1;i<=n;i++)...{
s.r[i].key=w[i-1];
}
}
voidshow(SqLists)...{
for(inti=1;i<=s.length;i++)...{
printf("%d ",s.r[i]);
}
printf(" ");
}
intselectMin(SqList&s,inti)...{
intkey=s.r[i].key;
intret=i;
for(intk=i;k<=s.length;k++)...{
if(key>s.r[k].key)...{
key=s.r[k].key;
ret=k;
}
}
returnret;
}
voidselectSort(SqList&s)...{
for(inti=1;i<=s.length;i++)...{
intj=selectMin(s,i);
if(i!=j)...{
RedTypetmp=s.r[i];
s.r[i]=s.r[j];
s.r[j]=tmp;
}
}
}
voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;
SqLists;
init(s,w,n);
selectSort(s);
show(s);
}
程序运行结果:
1327384949657697
Pressanykeytocontinue
算法的复杂度为O(n * n),主要是关键字的比较。
(2)堆排序
头文件:
#defineMAXSIZE20
#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))
typedefintKeyType;
typedefintInfoType;
typedefstruct...{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct...{
RedTyper[MAXSIZE+1];
intlength;
}HeapType;
源文件:
#include"sort.h"
#include"stdio.h"
voidinit(HeapType&s,intw[],intn)...{
s.length=n;
for(inti=1;i<=n;i++)...{
s.r[i].key=w[i-1];
}
}
voidshow(HeapTypes)...{
for(inti=1;i<=s.length;i++)...{
printf("%d ",s.r[i]);
}
printf(" ");
}
//adjusttheheapfromstom,tobeamaxheap.
voidheapAdjust(HeapType&h,ints,intm)...{
RedTyperc=h.r[s];
for(intj=2*s;j<=m;j*=2)...{
if(j<m&<(h.r[j].key,h.r[j+1].key))...{
j++;
}
if(!LT(rc.key,h.r[j].key))...{
break;
}
h.r[s]=h.r[j];
s=j;
}
h.r[s]=rc;
}
voidheapSort(HeapType&h)...{
//constructtheheap
for(inti=h.length/2;i>0;i--)...{
heapAdjust(h,i,h.length);
}
for(i=h.length;i>1;i--)...{
RedTyperc=h.r[i];
h.r[i]=h.r[1];
h.r[1]=rc;
heapAdjust(h,1,i-1);
}
}
voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;
HeapTypeh;
init(h,w,n);
heapSort(h);
show(h);
}
程序执行结果:
1327384949657697
Pressanykeytocontinue
说明:
当n较小时,不值得用heapsort;最坏情况的复杂度为O(n * log(n))。
分享到:
相关推荐
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
数据结构之选择排序
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
数据结构排序数据结构排序数据结构排序数据结构排序
数据结构排序算法
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构上机:题目: 排序 输人10个整数,分别用希尔排序、快速排序、直接选择排序和归并排序实现由小到大排序并输出排序结果。
南昌大学科学技术学院实验报告,《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的:学习数据结构课程,旨在使学生学会分析研究数据对象的特性,学会数据的组织...
数据结构 排序算法 快速排序 堆排序 冒泡 选择排序 折半排序 希尔排序 归并排序 插入
数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择...
数据结构排序算法小结 数据结构排序算法小结
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以...本资料详细总结了数据结构排序问题的实现与分析,希望对大家能有所帮助。
起泡排序 直接插入排序 简单选择排序 快速排序 希尔排序 堆排序
c语言版本的数据结构的快速排序算法,适用于新手学习
数据结构排序实验报告.doc
数据结构--快速排序C++源代码,自己编写调试,代码简单易懂,不长
用函数实现简单选择排序,并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample Input 10...
1、链表排序 [问题描述] 建立一个...设计要求:利用随机函数产生10个样本,每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序,基数排序八种排序方法进行排序