数据结构(c语言版)题集答案 - 第十章 - 内部排序
更新时间:2023-10-25 18:05:01 阅读量: 综合文库 文档下载
第十章 内部排序 10.23
void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 {
k=L.length;
for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) {
L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 }
}//Insert_Sort1 10.24
void BiInsert_Sort(SqList &L)//二路插入排序的算法 {
int d[MAXSIZE]; //辅助存储 x=L.r .key;d =x; first=1;final=1;
for(i=2;i<=L.length;i++) {
if(L.r[i].key>=x) //插入前部 {
for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j];
d[j+1]=L.r[i].key; final++; }
else //插入后部 {
for(j=first;d[j]d[j-1]=d[j];
d[(j-2)%MAXSIZE+1]=L.r[i].key;
first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况 } }//for
for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去 L.r[j].key=d[i]; }//BiInsert_Sort 10.25
void SLInsert_Sort(SLList &L)//静态链表的插入排序算法 {
L.r[0].key=0;L.r[0].next=1;
L.r[1].next=0; //建初始循环链表 for(i=2;i<=L.length;i++) //逐个插入 {
p=0;x=L.r[i].key;
while(L.r[L.r[p].next].keyp=L.r[p].next; q=L.r[p].next; L.r[p].next=i; L.r[i].next=q; }//for
p=L.r[0].next; for(i=1;i{
while(pq=L.r[p].next; if(p!=i) {
L.r[p]<->L.r[i]; L.r[i].next=p; } p=q; }//for
}//SLInsert_Sort 10.26
void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序 {
change=n-1; //change指示上一趟冒泡中最后发生交换的元素 while(change) {
for(c=0,i=0;iif(a[i]>a[i+1]) {
a[i]<->a[i+1];
c=i+1; //c指示这一趟冒泡中发生交换的元素 }
change=c; }//while
}//Bubble_Sort1 10.27
void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 {
low=0;high=n-1; //冒泡的上下界 change=1; while(low{ change=0;
for(i=low;iif(a[i]>a[i+1]) {
a[i]<->a[i+1];
change=1; }
high--; //修改上界
for(i=high;i>low;i--) //从下向上起泡 if(a[i]{
a[i]<->a[i-1]; change=1; }
low++; //修改下界 }//while
}//Bubble_Sort2 10.28
void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次冒泡 {
int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
d=1;b[0]=0;b[ 2 ]=n-1; //d为冒泡方向的标识,1为向上,-1为向下 change=1; while(b[0]{ change=0;
for(i=b[1-d];i!=b[1+d];i+=d) //统一的冒泡算法 if((a[i]-a[i+d])*d>0) //注意这个交换条件 {
a[i]<->a[i+d]; change=1; }
b[1+d]-=d; //修改边界 d*=-1; //换个方向 }//while
}//Bubble_Sort3 10.29
void OE_Sort(int a[ ],int n)//奇偶交换排序的算法 {
change=1;
while(change) {
change=0;
for(i=1;iif(a[i]>a[i+1]) {
a[i]<->a[i+1]; change=1; }
for(i=0;iif(a[i]>a[i+1]) {
a[i]<->a[i+1];
change=1; }
}//while }//OE_Sort
分析:本算法的结束条件是连续两趟比较无交换发生 10.30
typedef struct { int low; int high;
} boundary; //子序列的上下界类型
void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法 {
low=1;high=L.length;
InitStack(S); //S的元素为boundary类型 while(low{
if(high-low>2) //如果当前子序列长度大于3且尚未排好序 {
pivot=Partition(L,low,high); //进行一趟划分 if(high-pivot>pivot-low) {
Push(S,{pivot+1,high}); //把长的子序列边界入栈 high=pivot-1; //短的子序列留待下次排序 } else {
Push(S,{low,pivot-1}); low=pivot+1; } }//if
else if(low{
Easy_Sort(L,low,high); //直接进行比较排序 low=high; //当前子序列标志为已排好序 }
else //如果当前子序列已排好序但栈中还有未排序的子序列 {
Pop(S,a); //从栈中取出一个子序列 low=a.low; high=a.high; }
}//while
}//QSort_NotRecurve
int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同 {
L.r[0]=L.r[low];
pivotkey=L.r[low].key; while(low{
while(low=pivotkey) high--;
L.r[low]=L.r[high]; while(lowlow++; L.r[high]=L.r[low]; }//while
L.r[low]=L.r[0]; return low; }//Partition
void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序 {
if(high-low==1) //子序列只含两个元素
if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high]; else //子序列含有三个元素 {
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high]; if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; }
}//Easy_Sort 10.31
void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前 {
low=0;high=n-1; while(low{
while(low=0) high--; //以0作为虚拟的枢轴记录 a[low]<->a[high];
while(lowa[low]<->a[high]; }
}//Divide 10.32
typedef enum {RED,WHITE,BLUE} color; //三种颜色
void Flag_Arrange(color a[ ],int n)//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列 {
i=0;j=0;k=n-1; while(j<=k) switch(a[j]) {
case RED: a[i]<->a[j]; i++; j++;
正在阅读:
数据结构(c语言版)题集答案 - 第十章 - 内部排序10-25
交互设计中的需求层次及设计策略探讨11-12
25m预应力混凝土空心板梁桥设计05-13
祁集中心学校节假日值班管理制度04-05
街头那把美丽的伞作文500字06-19
第3章8086的寻址方式和指令系统04-30
电子商务系统实验三01-08
福建农林大学食用菌选修课期末考试材料12-25
【你好!2019】快乐迎新年作文06-13
山东省“十二五”规划全文04-27
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 十章
- 数据结构
- 排序
- 内部
- 答案
- 语言
- 第一届正式会议主持稿
- 104规约
- 五言律诗大全
- 第7讲 城乡规划法(一)(2011年新版)
- SANGFOR - AC - 教育城域网解决方案 - 201207
- CMMI - PA - Training - Test - Questionaire - ML3 测试题与答案
- 西南交通大学篮球体育理论考试试题及答案
- 甲级单位编制馐专用设备项目可行性报告(立项可研+贷款+用地+2013案例)设计方案
- 人教版六年级数学上册期末试卷及答案
- 奉节县平皋中学高92届同学聚会通知
- 最概然分布、微观状态数及其相关问题
- 高考地理冲刺专题卷专题15人文地理综合模块(必修2)(含解析)
- 商务英语学习资料
- 某轿车盘式制动器设计与分析毕业设计论文
- 流通学作业第一次-图书流通
- 肌学知识点归纳 - 图文
- 山东正天环保科技有限公司
- 八(下)期末现代文阅读专项复习(含答案)
- 平地炸药库火工品押运流程
- 物化2010复习题(答案)