数据结构与算法 第12天（排序）

一、排序方法分类

按照数据存储介质：

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

外部排序：数据量较大、数据在外存(文件排序)

将数据分批调入内存排序，结果放到外存

按照比较器个数：

串行排序：单处理机(同一时刻比较一对元素)

并行排序：多处理机(同一时刻比较多对元素)

按主要操作：

比较排序：用比较的方法

插入排序、交换排序、选择排序、归并排序

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

按辅助空间：

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

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

按稳定性：

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

非稳定排序：不是稳定排序的方法。

例子：

排序的稳定性只对结构类型数据排序有意义，不能衡量一个算法的优劣

按自然性：

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

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

二、插入排序

类似于扑克牌插牌，便插入边排序

顺序法

每循环一次，需要比较两次，可以使用哨兵，简化算法

算法

二分法

希尔排序

缩小增量多遍插入排序

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

希尔排序是不稳定的

算法

三、交换排序

冒泡排序

每趟不断将记录两两比较，并按规则交换，每一趟排好一个，是稳定的

n个元素需要n-1趟，第m趟需要比较n-m次

算法

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

优化：某次没有交换就说明已经排好序了

给算法加一个标记

快速排序

不是原地排序，是一种不稳定的算法，是所有内排序中最优的

不适于对基本有序的序列排序，会退化成冒泡排序

思路

从后面找比49小的放前面，后面就会空一个

再从前面找一个比49大的放后面，前面就会空一个，以此类推

算法

四、选择排序

简单选择排序

在待排序的数据中选出最大(小)的元素放在其最终的位置，是不稳定排序

基本操作

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

算法

堆排序

概念

堆实质是满足完全二叉树的性质

完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点

不稳定

堆排序

大根堆的根是最大值，小根堆的值是最小值

实现堆排序需解决两个问题:

1、如何由一个无序序列建成一个堆?

对一个无序数列反复进行筛选

例子

2、如何在输出堆顶元素后，调整剩余元素为一个新的堆?

小根堆：

筛选算法

堆的建立

算法

五、归并排序

二路归并排序

思想：

将两个或两个以上的有序子序列“归并”为一个有序序列

是一个稳定排序

例子

归并树

算法

简单了解一下

六、基数排序

思想：

分配+收集

是稳定的

例子

在分别按照，十位百位分配收集，最终得到有序数列

七、各种排序比较

时间性能

空间性能

稳定性能