基本概念和排序方法概述

基本概念

• 排序：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成有序序列（由小到大或由大到小）的运算。
• 如果参加排序的数据结点包含多个数据域，那么排序往往宿舍针对其中某个域而言

排序方法的分类

1. 按数据存储介质：内部排序和外部排序

2. 按比较器个数：串行排序和并行排序

3. 按主要操作：比较排序和基数排序

4. 按辅助空间：原地排序和非原地排序

5. 按稳定性：稳定排序和非稳定排序

6. 按自然性：自然排序和非自然排序

按存储介质分类

• 内部排序：数据量不大、数据在内存，无需内外交换数据

• 外部排序：数据量较大、数据在外存（文件排序）

外部排序时，要将数据分批调入内存来排序，中间结果还要及时存入外存，显然外部排序要复杂得多。

按比较器个数分类

• 串行排序：单处理器（同一时刻比较一对元素）

• 并行排序：多处理器（同一时刻比较多对元素）

按主要操作分类

• 比较排序：用比较的方法（插入排序、交换排序、选择排序、归并排序）

• 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。

按辅助空间分类

• 原地排序：辅助空间用量为O(1)的排序方法

所占的辅助存储空间与参加排序的数据量大小无关

• 非原地排序：辅助空间用量超过O(1)的排序方法

按稳定性分类

• 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变

• 非稳定性排序：不是稳定排序的方法

按自然性分类

• 自然排序：输入数据越有序，排序的速度越快的排序方法

• 非自然排序：不是自然排序的方法

按排序依据原则

• 插入排序：直接插入排序、折半插入排序、希尔排序

• 交换排序：冒泡排序、快速排序

• 选择排序：简单选择排序、堆排序

• 归并排序：2-路归并排序

• 基数排序

按排序所需工作量

• 简单的排序方法：

• 先进的排序方法：

• 基数排序：

存储结构——记录序列以顺序表存储

插入排序

基本思想

• 每步将一个待排序的对象，按其关键码大小啊，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

即边插入边排序，保证子序列中随时都是排好序的。

基本操作：有序插入

• 在有序序列中插入一个元素，保持序列有序，有序长度不断增加。

• 起初，a[0]是长度为1的子序列。然后，逐一将a[1]至a[n-1]插入到有序子序列中。

有序插入方法

1. 在插入a[i]前，数组a的前半段（a[0]~a[i-1]）是有序段，后半段（a[i]~a[n-1]）是停留于输入次序的“无序段”。

2. 插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j()，将a[i]插入在a[j]的位置上。

插入位置图示

插入排序的种类

直接插入排序

• 直接插入排序——采用顺序查找法查找插入位置

• 直接插入排序，使用“哨兵”

• 直接插入排序算法

实现排序的基本操作有两个： 1、“比较”序列中两个关键字的大小； 2、“移动”记录

• 性能分析

• 平均情况

• 时间复杂度结论
1. 原始数据越接近有序，排序速度越快
2. 最坏的情况下（输入数据是逆有序的）：
3. 平均情况下，耗时差不多是最坏情况的一般：
4. 要提高查找速度
• 减少元素的比较次数
• 减少元素的移动次数

折半插入排序

• 查找插入位置时采用折半查找法

• 折半插入排序算法

• 折半插入排序——算法分析

• 当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差;

• 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少;

• 减少了比较次数，但没有减少移动次数

• 平均性能优于直接插入排序

时间复杂度为 空间复杂度为 是一种稳定的排序方法

希尔排序（Donald.L.Shell）

• 基本思想：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

• 例子

• 希尔排序思路

• 刚才的例子中：

• 希尔排序特点
1. 一次移动，移动位置较大，跳跃式地接近排序后的最终位置
2. 最后一次只需要少量移动
3. 增量序列必须是递减的，最后一个必须是1
4. 增量序列应该是互质的（互质：互为质数）

• 希尔排序算法（主程序）

• 希尔排序算法（其中某一趟的排序操作）

• 希尔排序算法分析

时间复杂度n和d的函数：~——经验公式； 空间复杂度为O(1)； 是一种不稳定的排序方法。

• 如何选择最佳d序列（目前尚未解决）
1. 最后一个增量值必须为1，无除了1之外的公因子
2. 不宜在链式存储结构上实现

交换排序

基本思想

• 两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

常见的交换排序方法

1. 冒泡排序

2. 快速排序

冒泡排序——基于简单交换思想

• 基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换

• 例子

• 冒泡排序排序过程（升序）

总结 1、n个记录，总共需要n-1趟 2、第m趟需要比较n-m次

• 冒泡排序算法

优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素

• 如何提高效率？
一旦某一趟比较时不出现记录交换，说明已经排好序了。

• 改进的冒泡排序算法

• 冒泡排序算法分析

• 冒泡排序的算法评价
1. 冒泡排序最好时间复杂度是
2. 冒泡排序最坏时间复杂度是
3. 冒泡排序平均时间复杂度是
4. 冒泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)
5. 冒泡排序是稳定的

快速排序——改进的交换排序

• 基本思想
1. 任取一个元素（如：第一个）为中心(pivot:枢轴、中心点)
2. 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
3. 对各个子表重新选择中心元素并依此规则调整（递归思想）
4. 直到每个子表的元素只剩一个

通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

1、每一趟的子表的形成是采用从两头向中间交替式逼近法 2、由于每趟中对各子表的操作都相似，可采用递归算法

• 快速排序算法

• 快速排序算法分析

可以证明，平均计算时间是 1、QSort(): 2、Partition(): 实验结果证明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个

• 快速排序不是原地排序

由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。（即使不用递归，也需要用用户栈） 1、在平均情况下：需要的栈空间 2、最坏的情况下：栈空间可达

• 快速排序是一种不稳定的排序方法

划分元素的选取是影响时间性能的关键； 输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法； 改变划分元素的选取方法，至多只能改变算法平均情况的下的世界性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是。

选择排序

简单选择排序

• 基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置

• 基本操作
1. 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
2. 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
3. 重复上述操作，共进行n—1趟排序后，排序结束

• 简单选择排序算法

• 简单选择算法分析

时间复杂度 记录移动次数 1、最好情况：0 2、最坏情况：3(n-1) 比较次数：

堆排序

• 堆的定义

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点

• 堆排序：若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列又重新建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序。

• 堆的调整：如何在输出堆顶元素后，调整剩余元素为一个新的堆？

1、输出堆顶元素之后，以堆中最后一个元素替代之； 2、然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换； 3、重复上述操作，直到叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”

• 筛选过程的算法描述

对一个无需序列反复“筛选”就可以得到一个堆

• 堆的建立
1. 单结点的二叉树是堆；
2. 在完全二叉树中所有以叶子结点（序号i>n/2）为根的子树是堆。

只需依次以序号为n/2，n/2-1,……,1的结点为根的子树均调整为堆即可

• 将初始无序的R[1]到R[n]建成一个小根堆

• 堆排序算法

• 算法性能分析

1、初始堆化所需时间不超过O(n) 2、排序阶段（不含初始堆化） a.一次重新堆化所需时间不超过 b.n-1次循环所需时间不超过

• 堆排序的特点

1. 不稳定排序；

2. 只能用于顺序结构。不能用于链式结构；

3. 初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为，相对于快速排序最坏情况下的而言是一个优点，当记录较多时较为高效。空间复杂度为O(1)。

归并排序

• 基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。

在内部排序中，通常采用的是2-路归并排序。 即：将两个位置相邻的有序子序列R[1..m]和R[m+1..n]归并为一个有序序列R[1..n]

整个归并排序仅需趟

• 归并排序算法（相邻两个有序子序列的归并）

• 归并排序算法（2-路归并排序）

• 归并排序算法分析

时间效率： 空间效率： 稳定性：稳定

各种排序算法比较

• 综合比较

引用