本章聚焦于数据结构中的作业排序问题，涵盖多种算法如冒泡、插入和快速排序，并提供详细的解题思路及答案解析。
排序作业选择题（每题2分，共22分）：
1. 若表R在排序前已按键值递增顺序排列，则哪种算法的比较次数最少？
A．直接插入排序 B．快速排序 C．归并排序 D．选择排序
2. 对各种内部排序方法来说，以下哪个陈述正确？
A．快速排序时间性能最佳 B．归并排序是稳定的排序方法
C．快速排序是一种选择排序 D．堆排序所用的辅助空间比较大
3. 排序算法的稳定性是指：
A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变。
B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变。
C．排序算法的性能与被排序元素的数量关系不大
D．排序算法的性能与被排序元素的数量关系密切
4. 下列序列中哪一个是大顶堆？
A. {4,5,3,2,1} B. {5,3,4,1,2}
C. {1,2,3,4,5} D. {1,2,3,5,4}
5．若将{3，2，5，4，1}排为升序，则实施快速排序一趟后的结果是？
A. {1，2，3，4，5}
B. {1，2，4，5，3}
C. {1，3，5，4,2}
D．{2,5,4,1,3}
6．若将{1,2,3,4,5,6,7,9,8}排为升序，则哪种排序方法的“比较记录”次数最少？
A. 快速排序 B. 简单选择排序
C. 直接插入排序 D. 冒泡排序
7．若将{5，4，3，2，1}排为升序，则哪一种排序方法的“移动记录”次数最多？
A．快速排序 B．冒泡排序
C．直接插入排序 D．简单选择排序
8. 用简单选择排序将顺序表{2,3,1 ,3,2}（表示重复元素）排为升序，实施排序第一趟后结果是{1 ,3,2 ,3,2}, 则第三趟后的结果是什么？
A. {1 ,2,3 ,3′,2′} B.{ 1 ， 2 ， 2′， 3 ， 3′}
C．{1， 2， 2 ， 3 ， 3} D．{1， 2， 2， 3， 3}
9. 下列排序算法中，在某趟结束后不一定选出一个元素放到其最终位置上的排序方法是？
A.选择 B.冒泡 C.归并 D.堆
10．下列哪种排序算法是稳定的？
A．堆排序 B．直接插入排序 C．快速排序 D．希尔排序
11. 堆排序的时间复杂度为：
A.O(n*n) B.O(n*log n) C.O(n) D.O(log n)
填空题（每空4分，共4分）：
对n个元素进行归并排序时的空间复杂度是？
综合题（总24分）
1. （12分）有一组待排序的关键字如下：(54, 38, 96, 23, 15, 72, 60, 45，83) 分别写出希尔排序(d=5)，快速排序，堆排序和归并排序第一趟升序后的结果。（每种方法各占3分）
- 希尔排序：
- 快速排序：
- 堆排序：
- 归并排序：
2. （12分）已知数据序列是（12, 5，9，20，6，31，24），对该项数据进行升序排列。写出直接插入排序、简单选择排序、快速排序、堆排序和二路归并的第一次结果。（每种方法各占两分）
- 直接插入排序：
- 简单选择排序：
- 快速排序：
- 堆排序：
- 二路归并排
- 基数排序:（注释：原文中基数排序未给出具体序列，故此处保留原样）
5星
