c语言学习 排序详解.ppt

1， 排序1， 1 啥是 排序 1， 啥是 排序 将任一文件中的记录， 通过某种方式整理成按关键字递增(或递减)次序布列的操作环节. 假定给定 n 个记录的文件为 ( R1， R2， …， Rn ) 对应的关键字为 ( K1， K2， …， Kn ) 那么排序是 肯定似下一个布列 p1， p2， …， pn 使得 Kp1 ≤ Kp2 ≤ … ≤Kpn 从而得到一个有序文件 ( Rp1， Rp2， …， Rpn ) 1 排序1，1 啥是 排序 2， 啥是 排序的不乱性 假定在待排序的文件中， 存在两个具有同样关键字的记录 R(i)与R(j)， 其中 R(i) 位于 R(j) 以前. 在用某种排序法排序之后， R(i) 仍位于 R(j) 以前， 那么称这类排序方式是 不乱的；否那么， 称这类排序方式是 不不乱的. 例似， 给定数列 ( 10， 25， 22， 52， 25， 30， 18 ) 排序后， 如果为 ( 10， 18， 22， 25， 25， 30， 52 ) 那么称此环节是 不乱的排序； 排序后， 如果为 ( 10， 18， 22， 25， 25， 30， 52 ) 那么称此环节是 不不乱的排序. 1，6 排序1，6，1 啥是 排序 3， 排序方式 (1) 内部排序 如果被排序的文件较小， 那么可以将文件记录全部放在内存中， 合用于这类状况 的排序方式称为内部排序法. (2) 外部排序 如果被排序的文件非常大， 以致于不能同时将文件记录全部放在内存中， 而需要 将部分或全部记录存放在外存储器(磁盘、磁带等)中， 合用于这类状况的排 序方式称为外部排序法. 5， 考量一个排序算法利害的规格 (1) 对 n 个记录的文件排序所需对比关键字的次数； (2) 对 n 个记录的文件排序所需移动记录的次数； (3) 排序环节中所需的帮扶存储空间的大小. 在下述会商中商定： 文件的存储结构接收次序结构， 即使用一维数组 R[0..n] 中的 R[1，.n]示意 n 个记录的文件. 1，6，2 简单排序一、冒泡排序 算法根本理念 设待排序的文件为(R1， R2， …， Rn)，关键字为(R1，key， R2，key， …， Rn.key) 第 1 遍： 从 R(1) 最早， 依次对比两个相邻记录的关键字 R(i).key 和R(i＋1).key (ｉ＝1， 2， …， n－1). 如果 R(i).key＞R(i＋1).key， 那么交流相应记录 R(i) 和 R(i＋1)的存储位置；否那么， 不履行交流. 第1遍之后， n 个记录中关键字最大的记录移到了第 n 个位置上. 第 2 遍： 从 R(1) 最早， 依次对比两个相邻记录的关键字 R(i).key 和R(i＋1).key (ｉ＝1， 2， …， n－2). 如果 R(i).key＞R(i＋1).key， 那么交流相应记录 R(i) 和 R(i＋1)的存储位置；否那么， 不履行交流. 第2遍之后， 前 n－1 个记录中关键字最大的记