南京工业大学-数据结构-作业答案-作业7.doc
第七次作业
1.用某种排序方法对线性表（25,84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：
25,84，21,47,15,27,68,35,20→20,15,21,25，47,27,68,35,84→15,20,21,25，35,27,47,68,84→15,20,21,25，27,35,47,68,84，问采用的是什么排序方法？
2.对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？
3.以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？
①直接插入排序②希尔排序③冒泡排序④快速排序
⑤直接选择排序⑥堆排序⑦归并排序⑧基数排序（8分）
4.序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。
1.用某种排序方法对线性表（25,84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：
25,84，21,47,15,27,68,35,20→20,15,21,25，47,27,68,35,84→15,20,21,25，35,27,47,68,84→
15,20,21,25，27,35,47,68,84，问采用的是什么排序方法？
答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。
2.对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？
答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次
快速排序则看按什么数据来分子表。
如果按100来分，则很惨，也会是n(n-1)/2！
若按中间数据50或51来分表，则：
第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（21-1）
第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（22-1）
第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（23-1）
第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（24-1）
……
第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（26-1）
第7轮则能全部确定，（因为27=128），在100个子表中比较和交换了n－（100－1）个元素；
比较和交换总次数为：7n－(21－1＋22－1＋23－1……＋26－1＋100－1)＝7n+7－(1＋2＋4＋……＋64+100)=7n－(8+16+32+164)=700-220=480次
若从中间选择初始元素，则ASL=（n+1）log2n－(21＋22＋23+……＋2m)=nlog2n+log2n－(21＋22＋23+……＋n)≈O（nlog2n）
3.以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？
①直接插入排序②希尔排序③冒泡排序④快速排序
⑤直接选择排序⑥堆排序⑦归并排序⑧基数排序（8分）
解：先回答第2问：①⑤⑦⑧皆易于在链表上实现。
直接插入排序的中间过程如下：②希尔排序的中间过程如下：
冒泡排序的中间过程如下：④快速排序的中间过程如下：
直接选择排序的中间过程如下：⑥堆排序（大根堆）的中间过程如下：
归并排序排序的中间过程如下：
基数排序的中间过程如下：
4.序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。
10.42
typedefstruct{
intgt;//大于该记录的个数
intlt;//小于该记录的个数