数据结构课后答案 - 北邮 下载本文

1619253155294335113986869

4. 设有关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要求按照关键码值递增的次序进行排序。

(1) 若采用初时步长为4的Shell(希尔)排序法,写出一趟排序的结果;

(2) 若采用以第一个元素为分界元素(枢轴)的快速排序法,写出一趟排序的结果。 答案:

(1) (Q,A,C,S,Q,D,F,X,R,H,M,Y)

(2) (F,H,C,D,Q,A,M,Q,R,S,Y,X)

5. 试编写一个双向冒泡排序算法,即在排序过程中交替改变扫描方向。

6. 编写算法,实现将整形数组中的元素按照奇数和偶数分开,使奇数在原数组的前面,偶

数在原数组的后面。

7. 利用快速排序算法的思想,编写算法,实现求第k个最小值的功能。

8. 试写一个非递归的快速排序算法。

9. 如果存储结构采用的是带头结点的单链表,编写排序算法使链表中的元素有序排列。