[IT书籍]排序算法汇总.pdfVIP

第四讲排序算法 第一节 排序及其基本概念 一、基本概念 1．什么是排序 排序是数据处理中经常使用的一种重要运算。 设文件由n 个记录{R ，R ，……，R }组成，n 个记录对应的关键字集合为{K ，K ，……，K }。所谓排序就是将 1 2 n 1 2 n 这n 个记录按关键字大小递增或递减重新排列。 2．稳定性 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。 如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序之前的相对次序，则称 这种排序方法是稳定的；否则，称这种排序方法是不稳定的。 3．排序的方式 由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外部排序两类。整个排序过程 都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。 内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放人内存的大文件。 内排序是排序的基础，本讲主要介绍各种内部排序的方法。 按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。 二、排序算法分析 1．排序算法的基本操作 几乎所有的排序都有两个基本的操作： （1）关键字大小的比较。 （2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式 存储的记录则通过改变指向记录的指针实现重定位。 为了简化描述，在下面的讲解中，我们只考虑记录的关键字，则其存储结构也简化为数组或链表。并约定排 序结果为递增。 2．排序算法性能评价 排序的算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法 好坏的标准主要有两条： （1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度； （2）算法本身的复杂程度，比如算法是否易读、是否易于实现。 第二节 插入排序 插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，使 记录依然有序，直到所有待排序记录全部插入完成。 一、直接插入排序 1．直接插入排序的思想 假设待排序数据存放在数组A[1..n]中，则A[1]可看作是一个有序序列，让i 从2 开始，依次将A[i]插入到有序 序列A[1..i-1]中，A[n]插入完毕则整个过程结束，A[1..n]成为有序序列。 2．排序过程示例 （用【 】表示有序序列） 待排序数据： 【25】 54 8 54 21 1 97 2 73 15 （n=10） 54 54 i=2： 【25 5544】 8 54 21 1 97 2 73 15 8 8 i=3： 【88 25 54】 54 21 1 97 2 73 15 54 54 i=4： 【8 25 54 5544】 21 1 97 2 73 15 1 21 21 i=5： 【8 2211 25 54 54】 1 97 2 73 15 1 1 i=6： 【11 8 21 25 54 54】 97 2 73 15