排序

排序基本概念

  • 排序就是将一组数据元素序列重新排列，使得数据元素序列按某个数据项（关键字）有序。

    排序依据：是依据数据元素的关键字

​ 若关键字是主关键字（关键字值不重复），这无论采用何种排序方法，排出的结果都是唯一的；

若关键字是次关键词（关键字值可以重复），则排出的结果可能不唯一。![image-alt

稳定排序和不稳定排序

alt

内部排序和外部排序

  • 若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序；
  • 反之，若参见排序的记录数量很大，整个排序过程不可能在内存中完成，则称此类排序为外部排序。

alt

插入排序

基本思想

将无序子序列中的一个或几个记录“插入”到有序子序列中，从而增加有序子序列的长度。

alt

实现一趟插入排序可分三步进行：

alt

分类

  • 直接插入排序（基于顺序查找定位）
  • 折半插入排序（基于折半查找定位）
  • 希尔排序（基于逐趟缩小增量）

直接插入排序

排序过程

整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。

算法描述

alt

算法性能

alt

alt

==分析结果显示：用直接插入排序，数据序列越接近有序，比较次数越少。==

alt

希尔排序

基本思想

分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。

对待排记录序列先做宏观调整，再做微观调整。

宏观调整指的是“跳跃式”的插入排序

排序过程

  • 首先将记录序列分成若干个子序列；
  • 然后分别对每个子序列进行直接插入排序；
  • 最后待基本有序时，再进行一次直接插入排序。

alt

其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直到最后一趟排序减为1。

alt

alt

排序特点

alt

最坏复杂度分析

alt

Hibbard's增量序列

alt

算法性能

alt

选择排序

简单选择排序

基本思想

从无序子序列中选择关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列长度。

alt

排序过程

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

算法描述

alt

性能分析

alt

算法评价

alt

稳定性分析

alt

归并排序

合并2个有序表

alt

归并

将两个或两个以上的有序表组合成一个新的有序表，叫归并排序

排序过程

设初始序列含有n个记录，可以看做n个有序子序列，每个子序列长度为1，两两合并，得到二分之n个长度为2或1的有序子序列，再两两合并，。。。。。如此重复，直至得到长度为n的有序序列为止。

alt

迭代算法

  1. 将序列的每一个数据看成长度为1 的有序表；
  2. 然后将相邻两组进行归并得到长度为2的有序表（一趟归并）；
  3. 再对相邻两组长度为2的有序表进行下一趟归并得到长度为4的有序表；
  4. 如此一直进行下去，直到整个表归并成有序表。

如果某一趟归并过程中，单出一个表，该表轮空，等待下一趟归并。

递归思想

将无序序列划分成大概均等的2个子序列，然后用同样的方法对2个子序列进行归并得到2个有序的子序列，再用合并2个有序表的方法合并这2个子序列，得到n个元素的有序序列。

算法描述

alt

alt

算法评价

alt

alt

alt

交换排序

通过交换无序序列中的记录从而得到其中关键字最大或最小的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列长度

  • 冒泡排序
  • 快速排序

冒泡排序

排序过程

alt

alt

alt

代码实现

alt

算法评价

alt

算法优化

  1. 冒泡排序的结束条件为最后一趟没有进行交换记录
  2. 一般情况，每经过一趟冒泡，m-1，但并不是每趟都是如此。

alt

快速排序

算法思想

alt

alt

枢纽

alt

排序过程

alt

算法实现

alt

算法评价

alt

三者取中法

alt

算法特点

alt

算法分析

alt

alt

基数排序

多关键字排序

alt

高位优先多关键字排序

alt

alt

低位优先多关键字排序

alt

alt

==低位优先多关键字排序的实现更加简单，每趟排序都是一样无差别的操作，只不过排序因子不一样。==

链式基数排序

alt

alt

alt

顺序基数排序

alt

alt

alt

外部排序

大多数内排序算法都是利用了内存是直接访问的事实，读写一个数据是常量的时间。如果输入是在磁带上，磁带上的元素只能顺序访问，甚至数据是在磁盘上，效率还是下降。因为转动磁盘和移动磁头会产生延迟。

  • 外排模型
  • 预处理
  • 归并

外排序模型

  • 外排序具有设备依赖性。这里考虑的算法工作在磁带上；
  • 完成有效的排序至少需要两个磁带机；
  • 三个磁带机可以简化问题

外排序的基本方法

  • 由于一次外存操作所需的时间可以执行数百条甚至上千条指令，因此在外排序中我们考虑的是如何减少外存储器的读写；
  • 在外存上进行排序的最常用的方法就是利用归并排序，因为归并排序只需要访问被归并序列中的第一个元素，这里非常适合于顺序文件；
  • 外排序由两个阶段组成：
    • 预处理阶段：根据内存的大小将一个有n条记录的文件分批读入内存，用各种内排序算法排序，形成一个个有序片段；
    • 归并阶段：将这些有序片段逐步归并成一个有序文件。

预处理阶段

alt

alt

alt

alt

归并阶段

  • 两路归并
  • 多路归并
  • 多阶段归并
两路归并

alt

alt

alt

alt

alt

alt

多路归并

alt

alt

alt

alt

alt

多阶段归并

alt

alt

alt

alt