第九章 查找第十章 内部排序
void Insert_Sort(SqList &L)//监视哨设在高下标端的插入排序算法
{
k=Llength;
for(i=k;i;i) //从后向前逐个插入排序
if(Lr[i]key>Lr[i+]key)
{
Lr[k+]key=Lr[i]key; //监视哨
for(j=i+;Lr[j]key>Lr[i]key;++j)
Lr[j]key=Lr[j]key; //前移
Lr[j]key=Lr[k+]key; //插入
}
}//Insert_Sort
void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
int d[MAXSIZE]; //辅助存储
x=Lrkey;d=x;
first=;final=;
for(i=;i<=Llength;i++)
{
if(Lr[i]key>=x) //插入前部
{
for(j=final;d[j]>Lr[i]key;j)
d[j+]=d[j];
d[j+]=Lr[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].key p=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(p q=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;i if(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;i if(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;i if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
for(i=0;i if(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(low low++;
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(low a[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++;
break;
case WHITE:
j++;
break;
case BLUE:
a[j]<->a[k];
k--; //这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况
}
}//Flag_Arrange
分析:这个算法
