将哨兵放在R[n]中被排序的记录放在R[n]中重写直接插入排序算法解
重写的算法如下
void InsertSort(SeqList R)
{//对顺序表中记录R[n]按递增序进行插入排序
int ij;
for(i=n;i>=;i) //在有序区中依次插入R[n]R[]
if(R[i]key>R[i+]key) //若不是这样则R[i]原位不动
{
R[n]=R[i];j=i+; //R[n]是哨兵
do{ //从左向右在有序区中查找插入位置
R[j]=R[j]; //将关键字小于R[i]key的记录向右移
j++;
}while(R[j]key<R[n]key]);
R[j]=R[n]; //将R[i]插入到正确位置上
}//endif
}//InsertSort
以单链表作为存储结构实现直接插入排序算法
解
#define int KeyType //定义KeyType 为int型
typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域
struct node * next; //链表中指针域
}RecNode; //记录结点类型
typedef RecNode * LinkList ; //单链表用LinkList表示
void InsertSort(LinkList head)
{//链式存储结构的直接插入排序算法head是带头结点的单链表
RecNode *p*q*s;
if ((head>next)&&(head>next>next))//当表中含有结点数大于
{
p=head>next>next;//p指向第二个节点
head>next=NULL;
q=head;//指向插入位置的前驱节点
while(p)&&(q>next)&&(p>key<q>next>key)
q=q>next;
if (p)
{s=p;p=p>next;// 将要插入结点摘下
s>next=q>next;//插入合适位置q结点后
q>next=s;
}
}
}
设计一算法使得在尽可能少的时间内重排数组将所有取负值的关键字放在所有取非负值的关键字之前请分析算法的时间复杂度
解
因为只需将负数关键字排在前面而无需进行精确排列顺序因此本算法采用两端扫描的方法就象快速排序采用的方法一样左边扫描到正数时停止开始扫描右边遇到负数时与左边的当前记录交换如此交替进行一趟下来就可以完成排序
void ReSort(SeqList R)
{//重排数组使负值关键字在前
int i=j=n; //数组存放在R[n]中
while (i<j) //i<j表示尚未扫描完毕
{ while(i<j&&R[i]key<) //遇到负数则继续扫描
i++;
R[]=R[i]; //R[]为辅助空间
while(i<j&&R[j]key>=)// 遇到正数则继续向左扫描
j;
R[i++]=R[j];R[j]=R[];//交换当前两个元素并移动指针
}//endwhile
}//ReSort
本算法在任何情况下的比较次数均为n(每个元素和)相比交换次数少于n/总的来说时间复杂度为O(n)
*写一个双向冒泡排序的算法即在排序过程中交替改变扫描方向
解
算法如下
void BubbleSort(SeqList R)
{//R[n]是待排序文件双向扫描冒泡排序
int ijk;
Boolean exchange; //交换标记
i=n;j=;
exchange=TRUE;
while (i>j)&&(exchange)
{k=i;exchange=FALSE;
while (k>=j)//由下往上扫描
{if (r[k]>r[k+])
{r[]=r[k];r[k]=r[k+];r[k+]=r[k];exchange=TRUE;//交换
}//endif
k;
}//endwhile
if (exchange)
{exchange=FALSE;
j++;k=j+;
while(k<=i)//由上往下扫描
{if (r[k]<r[k])
{r[]=r[k];r[k]=r[k];r[k]=r[k];exchange=TRUE;//交换
}//endif
k++;
}endwhile
i;
}//endif
}endwhile
}//endsort
下面是一个自上往下扫描的冒泡排序的伪代码算法它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置并以它作为下一趟排序循环终止的控制值请仿照它写一个自下往上扫描的冒泡排序算法
void BubbleSort(int A[]int n)
//不妨设A[n]是整型向量
int lastExchangeji=n;
while (i>)
lastExchange=;
for(j=;j<i;j++)//从上往下扫描A[i]
if(A[j+]<A[j]){
交换A[j]和A[j+];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort
解算法如下
void BubbleSort(int A[]int n)
//不妨设A[n]是整型向量
int lastExchangeji=;
while (i<n) //这一条很重要如不改为这样算法将无限循环下去
lastExchange=n;
for(j=n;j>i;j)//从下往上扫描A[i]
if(A[j]<A[j]){
交换A[j]和A[j];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort
改写快速排序算法要求采用三者取中的方式选择划分的基准记录若当前被排序的区间长度小于等于时无须划分而是直接采用直接插入方式对其排序
解
改写后的算法如下
void QuickSort(SeqList Rint low int high)
{//对R[lowhigh]快速排序
int pivotpos;
if(highlow<=)//若当前区内元素少于个
{//则进行直接插入排序
InsertSort(Rlowhigh);
}
else
{
pivotpos=midPartion(Rlowhigh);
QuickSort(Rlowpivotpos);
QuickSort(Rpivotpos+high);
}
}//QuickSort
int midPartion(SeqList Rint i int j)
{//三者取中规则定基准
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+j)/]key)
{ 交换R[i]和R[(i+j)/];}
//以上三个if语句就使区间的第一个记录的key值为三个key的中间值
return Partion(Rij);//这样我们就可以仍使用原来的划分算法了
}
对给定的j(≤j≤n )要求在无序的记录区R[n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)试利用快速排序的划分思想编写算法实现上述的查找操作答
int QuickSort(SeqList Rint jint lowint high)
{ //对R[lowhigh]快速排序
int pivotpos //划分后的基准记录的位置
if(low<high){//仅当区间长度大于时才须排序
pivotpos=Partition(Rlowhigh) //对R[lowhigh]做划分
if (pivotpos==j) return r[j];
else if (pivotpos>j) return(Rjlowpivotpos);
else return quicksort(Rjpivotpos+high);
}
} //QuickSort
以单链表为存储结构写一个直接选择排序算法
答
#define int KeyType //定义KeyType 为int型
typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域
struct node * next; //链表中指针域
}RecNode; //记录结点类型
typedef RecNode * LinkList ; //单链表用LinkList表示
void selectsort(linklist head)
{RecNode *p*q*s;
if(head>next)&&(head>next>next)
{p=head>next;//p指向当前已排好序最大元素的前趋
while (p>next)
{q=p>next;s=p;
while(q)
{if (q>key<s>key) s=q;
q=q>next;
}//endwhile
交换s结点和p结点的数据
p=p>next;
}//endwhile
}//endif
}//endsort
写一个heapInsert(Rkey)算法将关键字插入到堆R中去并保证插入R后仍是堆提示应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述使其含有长度域)将key先插入R中已<
