将哨兵放在R[n]中
被排序的记录放在R[
n
]中
重写直接插入排序算法
以单链表作为存储结构实现直接插入排序算法
设计一算法使得在尽可能少的时间内重排数组将所有取负值的关键字放在所有取非负值的关键字之前请分析算法的时间复杂度
* 写一个双向冒泡排序的算法即在排序过程中交替改变扫描方向
下面是一个自上往下扫描的冒泡排序的伪代码算法它采用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
改写快速排序算法要求采用三者取中的方式选择划分的基准记录若当前被排序的区间长度小于等于时无须划分而是直接采用直接插入方式对其排序
对给定的j(≤j≤n )要求在无序的记录区R[n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)试利用快速排序的划分思想编写算法实现上述的查找操作
`以单链表为存储结构写一个直接选择排序算法
写一个heapInsert(Rkey)算法将关键字插入到堆R中去并保证插入R后仍是堆提示应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述使其含有长度域)将key先插入R中已有元素的尾部(即原堆的长度加的位置插入后堆的长度加)然后从下往上调整使插入的关键字满足性质请分析算法的时间
写一个建堆算法从空堆开始依次读入元素调用上题中堆插入算法将其插入堆中
写一个堆删除算法HeapDelete(Ri)将R[i]从堆中删去并分析算法时间提示先将R[i]和堆中最后一个元素交换并将堆长度减然后从位置i开始向下调整使其满足堆性质
已知两个单链表中的元素递增有序试写一算法将这两个有序表归并成一个递增有序的单链表算法应利用原有的链表结点空间
设向量A[n]中存有n个互不相同的整数且每个元素的值均在到n之间试写一时间为O(n)的算法将向量A排序结果可输出到另一个向量B[n]中
* 写一组英文单词按字典序排列的基数排序算法设单词均由大写字母构成最长的单词有d个字母提示所有长度不足d个字母的单词都在尾处补足空格排序时设置个箱子分别与空格ABZ对应
