二算法设计题
将哨兵放在R[n]中被排序的记录放在R[n]中重写直接插入排序算法
解重写的算法如下因为哨兵换了位置所以一切都反向了有序区是从右边长出来的;
void InsertSort(SeqList R)
{ file://对 顺序表中记录R[n]按递增序进行插入排序
int ij;
for(i=n;i>=;i) file://依 次插入R[n]R[]
if(R[i]key>R[i+]key) file://若 不是这样则R[i]原位不动
{
R[n]=R[i];j=i+; file://R [n]是哨兵
do{ file://从 左向右在有序区中查找插入位置
R[j]=R[j]; file://将 关键字小于R[i]key的记录向右移
j++;
}while(R[j]key
R[j]=R[n]; file://将 R[i]插入到正确位置上
}//endif
}//InsertSort
以单链表作为存储结构实现直接插入排序算法
解单链表?My God! 你还记得那是什么东东么? 先定义一个单链表结构吧
#define int KeyType file://且 定义KeyType 为int型的吧
typedef struct node{
KeyType key; file://关 键字域
OtherInfoType info; file://其 它信息域只是意思意思
struct node * next; file://链 表中指针域
}RecNode; file://记 录结点类型
typedef RecNode * RecList ; file://单 链表用RecList表示
file://下 面就是排序算法
void InsertSort(RecList R)
{ file://链 式存储结构的直接插入排序算法
file://R 是带头结点的单链表
RecNode *p*q*s*t; file://这 四个指针用于保存排序时的结点位置
s=R>next; file://s 指向第一个结点
t=R; file://t 指向头结点
p=R>next; file://前 一个记录
q=P>next; file://下 一个记录
while( q ) file://当 q为空时表示已经访问完毕所有结点排序结束
{
if(p>key>q>key)//此时前一关键字大于后一关键字因此要进行插入操作
{
while (s>key<=q>key&&s!=p)
{ file://从 头向右逐个比较直到p结点
t=s; file://记 下s结点位置
s=s>next; file://指 针向右移
}//比较结束找到比q>key大的第一个结点(记录)
t>next=q; file://摘 下q所指结点插入到相应位置
P>next=q>next;
q>next=s;
q=p>next; file://恢 复指针顺序
S=R>next;
t=R;
}//endif
else file://此 时没有插入操作指针按序右移
{p=p>next; q=q>next;}
}//endwhile
}//InsertSort
设计一算法使得在尽可能少的时间内重排数组将所有取负值的关键字放在所有取非负值的关键字之前请分析算法的时间复杂度
解因为只需将负数关键字排在前面而无需进行精确排列顺序因此本算法采用两端扫描的方法就象快速排序采用的方法一样左边扫描到正数时停止开始扫描右边遇到负数时与左边的当前记录交换如此交替进行一趟下来就可以完成排序
void ReSort(SeqList R)
{
file://重 排数组使负值关键字在前
int i=j=n; file://数 组存放在R[n]中
while (i file://i
{ while(i<) href=file://遇 file://遇 到负数则继续扫描
i++;
R[]=R[i]; file://R []为辅助空间
while(i=)// 遇到正数则继续向左扫描
j;
R[i++]=R[j];R[j]=R[];//交换当前两个元素并移动指针
}//endwhile
}//ReSort
本算法在任何情况下的比较次数均为n(每个元素和)相比交换次数少于n/总的来说时间复杂度为O(n)
*写一个双向冒泡排序的算法即在排序过程中交替改变扫描方向
解这个算法如下
void BubbleSort(SeqList R)
{ file://R [n]是待排序文件双向扫描冒泡排序
int ijk;
Boolean exchange; file://交 换标记
for(i=;i file://最 多只需(n/)趟排序
{
exchange=FLASE;
for(j=ni; j>=i;j) file://对 当前无序区R[ini+]进行自下而上扫描
{
if(R[j+]key file://轻 的泡泡上升
{
R[]=R[j+];
R[j+]=R[j];
R[j]=R[];
exchange=TURE; file://交 换后标记为真
}
if (!exchange) return; file://本 趟排序未发生交换提前结束
}//endfor
exchange=FLASE; file://重 新设置标记
for(k=i+; k<=ni;k++) file://对 当前无序区R[ini+]进行自上而下扫描
{
if(R[k+]key>R[k]key) file://重 的泡泡下沉
{
R[]=R[k+];
R[k+]=R[k];
R[k]=R[];
exchange=TURE; file://交 换后标记为真
}
if(!exchange) return; file://本 趟未发生交换提前结束
}//endfor
}//endfor
}//BubbleSort
下面是一个自上往下扫描的冒泡排序的伪代码算法它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置并以它作为下一趟排序循环终止的控制值请仿照它写一个自下往上扫描的冒泡排序算法
void BubbleSort(int A[]int n)
//不妨设A[n]是整型向量
int lastExchangeji=n;
while (i>)
lastExchange=;
for(j=;j
if([j+]
交换A[j]和A[j+];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort
解算法如下这种方向性的改变一般是一些加号要变为减号大于变成小于头一个结点变成最后一个结点如此这般
void BubbleSort(int A[]int n)
file://不 妨设A[n]是整型向量
int lastExchangeji=;
while (i file://这 一条很重要如不改为这样算法将无限循环下去
lastExchange=n;
for(j=n;j>i;j)//从下往上扫描A[i]
if([j]
交换A[j]和A[j];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort
改写快速排序算法要求采用三者取中的方式选择划分的基准记录;若当前被排序的区间长度小于等于时无须划分而是直接采用直接插入方式对其排序
解改写后的算法如下
void QuickSort(SeqList Rint low int high)
{ file://对 R[lowhigh]快速排序
int pivotpos;
if(highlow<=) file://若 当前区内元素少于个
{ file://则 进行直接插入排序
InsertSort(Rlowhigh);//此函数就不写了
}
else
{
pivotpos=midPartion(Rlowhigh);
QuickSort(Rlowpivotpos);
QuickSort(Rpivotpos+high);
}
}//QuickSort
int midPartion(SeqList Rint i int j)
{ file://三 者取中规则定基准
if(R[(i+j)/]key>R[i]key)
{ 交换R[(i+j)/]和R[i];}
if(R[i]key>R[j]key)
{ 交换R[i]和R[j];}
if(R[i]key)
{ 交换R[i]和R[(i+j)/];}
file://以 上三个if语句就使区间的第一个记录的key值为三个key的中间值
return Partion(Rij);//这样我们就可以仍使用原来的划分算法了
}
顺便提一下课本中又有几处笔误如第页的算法中A[i]A[k]应为R[i]R[k]以及下面的算法中递归调用的应是RandomizedQuickSort函数而不是QuickSort函数
另外这些算法并不能直接用于验证因为算法中用的都不是指针参数而算法又要对实参进行修改才能达到所需结果所以我们主要是要理解算法的整个思想和实现真正编程的话要上机多试才行
对给定的j( ≤ j ≤ n )要求在无序的记录区R[n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)试利用快速排序的划分思想编写算法实现上述的查找操作
(答案及点评) 以单链表为存储结构写一个直接选择排序算法
(答案及点评) 写一个heapInsert(Rkey)算法将关键字插入到堆R中去并保证插入R后仍是堆提示应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述使其含有长度域);将key先插入R中已有元素的尾部(即原堆的长度加的位置插入后堆的长度加)然后从下