排序常用算法设计(2)

for(j=0;ji=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 时，无须划分而是直接采用直接插入方式对其排序。

课后答案网 www.khdaw.com 解： 改写后的算法如下：

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 个最小元)，试利用快速排序的划分思想编写算法实现上 述的查找操作。

课后答案网 www.khdaw.com

答： 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) {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->keykey) s=q; q=q->next; }//endwhile

交换s 结点和p 结点的数据； 课后答案网 www.khdaw.com p=p->next; }//endwhile }//endif }//endsort

21.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提

示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度

域)；将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，

然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 答： #define n 100//假设文件的最长可能长度 typedef int KeyType; //定义KeyType 为int 型 typedef struct node{ KeyType key; //关键字域

OtherInfoType info; //其它信息域， }Rectype; //记录结点类型 typedef struct{

Rectype data[n] ; //存放记录的空间 int length;//文件长度