[研究生入学考试]Ch9 排序.pdf

排序 曹迎春 yccao@nju.edu.cn 排序的基本概念  假设有n个数据元素的序列{R1 , R2 , … , Rn}， 其相应关键字的序列是{K1 , K2 , … , Kn}，通过 排序要求找出下标1 , 2 , … , n的一种排列p1 , p2 , … , pn ，使得相应关键字满足如下的非递减 （或 非递增）关系 Kp1 ≤ Kp2 ≤ … ≤ Kpn 这样，就得到一个按关键字有序的纪录序列：{ Rp1 , Rp2 , … , Rpn }。 2011/2/28 2 排序的基本概念  排序的分类  内部排序  整个排序过程在内存储器中进行  外部排序  待排序元素数量太大，排序需要借助外部存储设备才能完成 2011/2/28 3 排序的基本概念  如果在待排序的序列中存在多个具有相同关键字 的元素。假设Ki Kj （1≤ i≤ n ，1≤ j≤ n，i≠j ）， 若在排序之前的序列中Ri在Rj之前，经过排序后 得到的序列中Ri仍然在Rj之前，则称所用的排序 方法是稳定的；否则，当相同关键字元素的前后 关系在排序中发生变化，则称所用的排序方法是 不稳定的。 2011/2/28 4 排序方法  插入排序  交换排序  选择排序  归并排序 2011/2/28 5 插入类排序  逐个考察每个待排序元素，将每一个新元素插入 到前面已经排好序的序列中适当的位置上，使得 新序列仍然是一个有序序列。  主要有三种：  直接插入排序  折半插入排序  希尔排序 2011/2/28 6 直接插入排序  基本思想：  仅有一个元素的序列总是有序的，因此，对n 个记录 的序列，可从第二个元素开始直到第n 个元素，逐个 向有序序列中执行插入操作，从而得到n 个元素按关 键字有序的序列。 2011/2/28 7  对关键字序列{ 26 , 53 , 48 , 11 , 13 , 48 , 32 , 15} 进行排序。 2011/2/28 8 insertSort 2011/2/28 9 算法分析  空间效率  仅使用一个辅存单元  时间效率  最好情况 总比较次数=n-1 总移动次数=0  最坏情况