(1)直接插入
算法的复杂度O(n * n)。
头文件:
#defineMAXSIZE20
#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))
typedefintKeyType;
typedefintInfoType;
typedefstruct...{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct...{
//r[0]isthesentinel,notused.
RedTyper[MAXSIZE+1];
intlength;
}SqList;
源文件:
#include"stdio.h"
#include"sort.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(" ");
}
voidinsert(SqList&s)...{
for(inti=2;i<=s.length;i++)...{
if(LT(s.r[i].key,s.r[i-1].key))...{
//setthesentinel
s.r[0]=s.r[i];
s.r[i]=s.r[i-1];
for(intj=i-2;LT(s.r[0].key,s.r[j].key);j--)...{
s.r[j+1]=s.r[j];
}
s.r[j+1]=s.r[0];
}
}
}
voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;
SqLists;
init(s,w,n);
insert(s);
show(s);
}
执行结果:
1327384949657697
Pressanykeytocontinue
(2)减少比较次数-折半插入
源文件添加:
//usethebinarysearchmethodtofindthelocationtoinsert.
voidbinaryInsert(SqList&s)...{
for(inti=2;i<=s.length;i++)...{
//setthesentinel
s.r[0]=s.r[i];
//binarysearchthelocationtoinsert
intlow=1,high=i-1;
intm;
while(low<=high)...{
m=(low+high)/2;
if(LT(s.r[0].key,s.r[m].key))...{
high=m-1;
}else...{
low=m+1;
}
}
for(intj=i-1;j>=high+1;j--)...{
s.r[j+1]=s.r[j];
}
s.r[high+1]=s.r[0];
}
}
折半插入仅减少了比较次数,而记录的移动次数没变。
(3)减少移动次数-表插入排序
头文件:
#defineSIZE100
#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))
typedefintKeyType;
typedefintInfoType;
typedefstruct...{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct...{
RedTyperc;
intnext;
}SLNode;
typedefstruct...{
//r[0]isheadofstaticlist
SLNoder[SIZE];
intlength;
}SLinkListType;
源文件:
#include"stdio.h"
#include"SLLInsert.h"
voidinit(SLinkListType&s,intw[],intn)...{
s.length=n;
for(inti=1;i<=n;i++)...{
s.r[i].rc.key=w[i-1];
//pointtothehead,touser[o]asasentinal
s.r[i].next=0;
}
s.r[0].next=1;
}
voidshow(SLinkListTypes)...{
for(inti=0;i<=s.length;i++)...{
printf("%d:%d(%d) ",i,s.r[i].rc.key,s.r[i].next);
}
printf(" ");
}
voidinsert(SLinkListType&s)...{
intparent,next;
for(inti=2;i<=s.length;i++)...{
s.r[0].rc.key=s.r[i].rc.key;
parent=0;
next=s.r[parent].next;
while(LT(s.r[next].rc.key,s.r[0].rc.key))...{
parent=next;
next=s.r[next].next;
}
//insert
s.r[i].next=next;
s.r[parent].next=i;
}
}
voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;
SLinkListTypes;
init(s,w,n);
insert(s);
show(s);
}
程序执行结果:
0:49(6)1:49(3)2:38(8)3:65(5)4:97(0)
5:76(4)6:13(7)7:27(2)8:49(1)
Pressanykeytocontinue
表插入并没有减少比较次数,故复杂度仍为O(n * n)。
(4)shell排序
子序列的构成不是简单的“逐段分割”,而是将相隔某个“增量”的记录组成一个子序列。
源文件添加:
//onepassofshellsort
voidshellInsert(SqList&s,intdk)...{
intj;
for(inti=dk+1;i<=s.length;i++)...{
if(LT(s.r[i].key,s.r[i-dk].key))...{
s.r[0]=s.r[i];
for(j=i-dk;j>0&<(s.r[0].key,s.r[j].key);j-=dk)...{
s.r[j+dk]=s.r[j];
}
s.r[j+dk]=s.r[0];
}
}
}
voidshellSort(SqList&s,intdlta[],intt)...{
for(intk=0;k<t;k++)...{
shellInsert(s,dlta[k]);
}
}
voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;
intdlta[]=...{5,3,1};
intt=3;
SqLists;
init(s,w,n);
//binaryInsert(s);
shellSort(s,dlta,t);
show(s);
}
程序执行结果:
1327384949657697
Pressanykeytocontinue
注意:增量序列中 dlta[] 没有除了1以外的公因子,并且最后一个增量值必须等于1。
分享到:
相关推荐
数据结构排序插入排序和交换排序PPT学习教案.pptx
用函数实现折半插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 5...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
数据结构排序算法中的折半插入排序,又称二分法,是对基本插入排序的一种改进,比普通的插入排序要快
数据排序中的一种最基本的排序算法 比较次数个移动次数约为n的平凡除4, 时间复杂度约为0(n的平凡)
本事例中将插入排序和选择排序合并在一个程序里,直观明了,程序简单易懂,是学习数据结构很好的互补
南昌大学科学技术学院实验报告,《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的:学习数据结构课程,旨在使学生学会分析研究数据对象的特性,学会数据的组织...
数据结构中的排序方法 属于内部排序 直接插入排序
数据结构用直接插入的方式排序,编写一个程序实现直接插入排序算法。
数据结构课程中直接插入排序的示例程序 完整示例
数据结构 排序算法 快速排序 堆排序 冒泡 选择排序 折半排序 希尔排序 归并排序 插入
数据结构中经典的插入法排序,注释详尽,调试有效,希望能帮到大家~
数据结构报告c++,简单选择排序,冒牌排序,插入排序,快速排序,两路合并排序,堆排序,几种排序方法的比较,有详细的源代码和实验报告
2. (共12分)已知数据序列为(12,5,9,20,6,31,24),对该项数据序列进行排序,分别写出直接插入排序、简单选择排序、快速排序、堆排序、二路归并排序及基数排序第一趟升序排序结果(其中堆排序的第一趟指序列...
数据结构中的折半插入排序算法用C语言来实现的完整示例程序
掌握二叉树链表的结构和二叉排序树的建立过程; 掌握二叉排序树的插入和删除操作; 3、加深对二叉树的理解,逐步培养解决实际问题的编程能力 一)基础题 1、编写二叉排序树的基本操作函数 (1)SearchNode( TREE *...
《数据结构》严蔚敏版 折半插入排序