第8章排序(算法设计)习题练习

第8章排序(算法设计)习题练习  

以单链表作为存储结构实现直接插入排序算法  

设计一算法 使得在尽可能少的时间内重排数组 将所有取负值的关键字放在所有取非负值的关键字之前 请分析算法的时间复杂度  

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

下面是一个自上往下扫描的冒泡排序的伪代码算法 它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置 并以它作为下一趟排序循环终止的控制值 请仿照它写一个自下往上扫描的冒泡排序算法 void BubbleSort(int A[] int n)　//不妨设A[ n ]是整型向量　int lastExchange j i=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 

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

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

`以单链表为存储结构 写一个直接选择排序算法

写一个heapInsert(R key)算法 将关键字插入到堆R中去 并保证插入R后仍是堆 提示 应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述 使其含有长度域) 将key先插入R中已有元素的尾部(即原堆的长度加 的位置 插入后堆的长度加 ) 然后从下往上调整 使插入的关键字满足性质 请分析算法的时间

写一个建堆算法 从空堆开始 依次读入元素调用上题中堆插入算法将其插入堆中

写一个堆删除算法 HeapDelete(R i) 将R[i]从堆中删去 并分析算法时间 提示 先将R[i]和堆中最后一个元素交换 并将堆长度减 然后从位置i开始向下调整 使其满足堆性质

已知两个单链表中的元素递增有序 试写一算法将这两个有序表归并成一个递增有序的单链表 算法应利用原有的链表结点空间

设向量A[ n ]中存有n个互不相同的整数 且每个元素的值均在 到n 之间 试写一时间为O(n)的算法将向量A排序 结果可输出到另一个向量B[ n ]中