数据结构课后答案 - 北邮

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. 如果存储结构采用的是带头结点的单链表，编写排序算法使链表中的元素有序排列。