中南大学数据结构与算法第10章内部排序课后作业答案

*16.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 解：

算法如下：

void BubbleSort(SeqList R)

{//R[1..n]是待排序文件，双向扫描冒泡排序 int i,j,k;

Boolean exchange; //交换标记 i=n;j=1; exchange=TRUE; while (i>j)&&(exchange) {k=i-1;exchange=FALSE; while (k>=j)//由下往上扫描 {if (r[k]>r[k+1])

{r[0]=r[k];r[k]=r[k+1];r[k+1]=r[k];exchange=TRUE;//交换 }//endif k--; }//endwhile if (exchange) {exchange=FALSE; j++;k=j+1;

while(k<=i)//由上往下扫描 {if (r[k]

{r[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交换 }//endif k++; }endwhile i--; }//endif }endwhile }//endsort

17.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。

void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0;

for(j=0;j

i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort

解：算法如下：

void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=0;

while (i

for(j=n-1;j>i;j--)//从下往上扫描A[0..i] if(A[j-1]

i=lastExchange;//将i置为最后交换的位置

}//endwhile }//BubbleSort

18.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 解：

改写后的算法如下：

void QuickSort(SeqList R,int low ,int high) {//对R[low..high]快速排序 int pivotpos;

if(high-low<=2)//若当前区内元素少于3个 {//则进行直接插入排序 InsertSort(R,low,high); } else {

pivotpos=midPartion(R,low,high); QuickSort(R,low,pivotpos-1); QuickSort(R,pivotpos+1，high); } }//QuickSort

int midPartion(SeqList R,int i, int j) {//三者取中规则定基准 if(R[(i+j)/2].key>R[i].key) { 交换R[(i+j)/2]和R[i];} if(R[i].key>R[j].key) { 交换R[i]和R[j];} if(R[i].key)

//以上三个if语句就使区间的第一个记录的key值为三个key的中间值 return Partion(R,i,j);//这样我们就可以仍使用原来的划分算法了 }

19.对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 答：

int QuickSort(SeqList R,int j,int low,int high) { //对R[low..high]快速排序

int pivotpos； //划分后的基准记录的位置 if(low

pivotpos=Partition(R，low，high)； //对R[low..high]做划分 if (pivotpos==j) return r[j];

else if (pivotpos>j) return(R,j,low,pivotpos-1); else return quicksort(R,j,pivotpos+1,high); } } //QuickSort

20.以单链表为存储结构，写一个直接选择排序算法。 答：

#define int KeyType //定义KeyType 为int型 typedef struct node{

KeyType key; //关键字域

OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 }RecNode; //记录结点类型

typedef RecNode * LinkList ; //单链表用LinkList表示

void selectsort(linklist head)