数据结构(c语言版)题集答案——第十章_内部排序

第十章 内部排序 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];