外部排序通常采用归并排序法

发布时间：2025-06-24 20:57:35  作者：北方职教升学中心  阅读量：338

中心点）

所有比它小的元素一律前方，比它大的一律后放，形成两个子表；

对各个子表重新选择中心元素并以此规则调整；

直到每个子表的元素只剩下一个

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

具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。

1. 每一趟的子表的形成是采用从两头向中间交替式逼近法；

2. 由于每趟中对各子表的操作都相似，可采用递归算法。由于外村信息的读/写是以“磁盘块”为单位进行的，以8个归并段为例，可知每一趟归并需进行16次读和16次写，3趟归并并加上内部排序时所需进行的读/写，使得总共需进行128次读写。

3. 简单选择排序、

   顺序表查找法

   从后往前找就可以了。在插入第i个对象时，需要经过|Iog2 i|+1次关键码比较，才能确定它应插入的位置；

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

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

   3.希尔排序

   基本思想：

   先将整个待排记录序列分割成若子序刻，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
   外部排序通常采用归并排序法。写入磁盘，而这会耗费大量的时间。归并排序

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

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

   堆的调整：

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

   小根堆：

   1. 输出堆顶元素之后，以堆中最后一个元素替代之：

   2. 然后将根结点值与左、

      特点：1. 缩小增量 2. 多遍插入排序

      1. 一次移动，移动位置较大，跳跃式地接近排序后的最终位置

      2. 最后一次只需要少量移动

      3. 增量序列必须是递减的，最后一个必须是1

      4. 增量序列应该是互质的

      void ShellInsert(SqList &L, int dk){    //对顺序表L进行增量为dk的Shell排序，dk为步长因子    for(i = dk+k;i <= L.length; ++i)    {        if(r[i].key < r[i-dk].key)        {            r[0] = r[i];            for(j = i-dk;j > 0 && (r[0].key < r[i].key); j = j-dk)            {                r[j+dk] = r[j];            }            r[j+dk] = r[0];        }    }}​void ShellSort(SqList &L, int dlta[], int t){    //按增量序列dlta[0……t-1]对顺序表L作希尔排序    for(k = 0;k < t; ++k)    {        ShellInsert(L, dlta[k]);//一趟增量为dlta[k]的插入排序    }}

      希尔排序算法效率与增量序列的取值有关

      Hibbard增量序列

      1. Dk=2k-1——相邻元素互质

      2. 最坏情况：Tworst=O(n3/2)

      3. 猜想：Tavg=O(n5/4)

      Sedgewick增量序列{1, 5, 19, 41, 109, …}

      ——9* 4i-9 * 2i+1 或 4-3 * 2i + 1

      猜想：Tavg=O(n7/6) Tworst=O(n4/3)

      希尔排序法是一种不稳定的排序算法

      

      我们发现有两个值是相等的，它们两个数的位置发生了变化

      时间复杂度是n和d的函数：

      O(n1.25) ~ O(1.6n1.25) 一 经验公式

      空间复杂度为O(1)

      1. 如何选择最佳d序列，目前尚未解决

      2. 最后一个增量值必须为1，无除了1之外的公因子

      3.交换排序

      基本思想：两两比较，如果发生逆序则交换，知道所有记录都排好序为止。堆排序和归并排序的时间性能不随记录序列中关键字的 分布而改变。

      常见的交换排序方法：

      1. 冒泡排序 O(n2)

      2. 快速排序 O(nlog2n)

      1.冒泡排序

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

      例：6个记录 21, 25, 49, 25* , 16, 08

      第1趟结束：21, 25, 25* , 16, 08, 49

      第2趟结束：21, 25, 16, 08, 25* , 49

      第3趟结束：21, 16, 08, 25, 25* , 49

      第4趟结束：16, 08, 21, 25, 25* , 49

      第5趟结束：08, 16, 21, 25, 25* , 49

      void bubble_sort(SqList &L){    //冒泡排序算法    int m,i,j;    Redtype x;//交换时临时存储    for(m = 1;m < n; m++)    {        if(L.r[j].key > L.r[j+1].key)        {            //发生逆序            x = L.r[j];            L.r[j] = L.r[j+1];            L.r[j+1] = x;        }    }}

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

      提高效率：一旦某一趟比较时不出现记录交换，说明已经排好序，就可以结束算法。

      稳定性：稳定

      5.基数排序

      基本思想：分配+收集

      也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后再按序号将非空的连接。

      空间复杂度：

      快速排序不是原地排序

      由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。

      对于不稳定的排序方法，只要能举出一个实例说明即可。

      按自然性：

      自然排序和非自然排序

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

      由于堆的实质上是一个线性表，那么我们就可以顺序存储一个堆。

      这种方法适合要排序的数据太多，以至于内存一次性装载不下。交换排序、堆排序在最坏情况下，其时间复杂度也为O(log2n)，这是堆排序的最大优点。因此，需要将待排序的记录存储在外存中，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换。冒泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；

      时间复杂度为O(n)的排序方法只有：基数排序。(所占的辅助存储空间与参加排序的数据量大小无关)

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

      即，将无序序列排成一个有序序列（由小到大或由大到小）的运算。
      对这些归并段进行逐趟归并，是归并段逐渐由小到大，直至得到整个有序文件位置。

      (枢轴)中间数：可以是第一个数、

      快速排序和堆排序是不稳定的排序方法。希尔排序

   3. 交换排序：冒泡排序、

      4.关于“排序方法的时间复杂度的下限“

      本章讨论的各种排序方法，除基数排序外，其它方法都是基于“"比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。
      因此增大归并路数可以减少归并趟数，进而减少总的磁盘I/O次数。
      在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时存放在内存中，因此需要不停地将数据读出、

      非自然排序：不是自然排序的方法。（即使不用递归，也需要用用户栈）

      1. 在平均情况下：需要O(logn)的栈空间

      2. 最坏情况下：栈空间可达O(n)。冒泡和简单选择）和堆排序的空间复杂度为O(1)

      3. 快速排序为O(logn)，为栈所需的辅助空间

      4. 归并排序所需辅助空间最多，其空间复杂度为O(n)

      5. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)

      3.排序方法的稳定性能

      稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。

      按比较器个数：

      串行排序和并行排序

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

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

      按主要操作：

      比较排序和基数排序

      比较排序：比较的方法，插入排序、

   堆排序思想

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

   按辅助空间：

   原地排序和非原地排序

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

   时间效率：O(k*(n+m))，k：关键字个数，m：关键字取值范围为m个值

   基数排序是一个稳定的排序

   例如：10000个人按照生日排序

   年 月 日 3个关键字

   假设取值范围分别是：1930~2018 1~ 12 1~31 0(n2)≈108 O(nlogn)≈105

   0(k*(n+m)) ≈ (10000+89)+(10000+12)+(10000+31) ≈ 104

   6.外部排序

   在内存中进行的排序是内部排序，而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、

   用一个示例来介绍小根堆的过程：

   有关键字为49, 38, 65, 97, 76, 13, 27, 49的一组数据，将其按照关键字调整为一个小根堆。一般情况下：
   外部排序的总时间 = 内存排序所需的时间 + 外存信息读取的时间 + 内部归并所需的时间
   显然，外村信息读取地时间远大于内部排序和内部归并地的时间，因此应着力减少I/O次数。

   堆的建立：

   显然：单节点的二叉树是堆；在完全二叉树中所有以叶子结点（序号i ＞ n/2）为根的子树是堆。

   1. 赋值插入元素

   2. 记录后移，查找插入元素

   3. 插入到正确位置

   x = a[i];for(j = i - 1;j >= 0 && x < a[j]; j--){    a[j+1] = a[j];}a[j-1] = x;

   或者使用“哨兵”来辅助实现插入的工作，

   1. 复制哨兵

   2. 记录后移，查找插入位置

   3. 插入到正确位置

   L.r[0] = L.r[i];for(j = i - 1;L.r[0].key < L.r[j].key; --j){    L.r[j+1] = L.r[j];}L.r[j+1] = L.r[0]

   【直接插入算法】

   void InsertSort(SqList &L){    int i, j;    for(i = 2;i <= L.length; ++i)    {        if(L.r[i].key < L.r[i-1])        {            //如小于，则将L.r[i]插入有序子表            L.r[0] = L.r[i];//复制哨兵            for(j = i-1;L.r[0].key < L.r[i].key; --j)            {                L.r[j+1] = L.r[j];//记录后移            }            L.r[j+1] = L.r[0];//插入到正确位置        }    }}

   实现排序的基本操作有两个：

   1. “比较”序列中两个关键字的大小；

   2. “移动”记录；

   最好的情况（关键字在记录序列中顺序有序）

   最坏的情况（关键字在记录序列中逆序有序）

   时间复杂度：

   原始数据越接近有序，排序速度越快

   最坏情况下（输入数据是逆有序的）Tw(n) = O(n^2)

   平均情况下，耗时差不多是最坏情况的一半 Te(n) = O(n^2)

   要提高查找速度

   1. 减少元素的比较次数

   2. 减少元素的移动次数

   2.折半插入排序

   前提是对已经排过序的数据进行插入操作

   【折半插入排序算法】

   void BInsertSort(SqList &L){    for(i = 2;i <= L.length; ++i)    {        //依次插入第2个~第n个元素        L.r[0] = L.r[i];//当前插入元素存到“哨兵”位置        low = 1;        high = i - 1;//采用二分查找法插入位置        while(low <= high)        {            mid = (low+high) / 2;            if(L.r[0].key < L.r[mid].key) high = mid - 1;            else low = mid + 1;        }//循环结束，high+1则为插入位置        for(j = i - 1;j >= high+1; --j)        {            //移动元素            L.r[j+1] = L.r[j];        }        L.r[high+1] = L.r[0];//插入到正确位置    }}

   折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快；

   它所需要的关键码比较次数与待排序对像序列的初始排列无关，仅依赖于对象个数。

   

    从最后一个非叶子结点开始，从此向前调整：

   1. 调整从第n/2个元素开始，将以该元素为根的二叉树调整为堆；

   2. 将以序号为n/2-1的结点为根的二叉树调整为堆；

   3. 再以序号为n/2-2的结点为根的二叉树调整为堆；

   4. 再以序号为n/2-3的结点为根的二叉树调整为堆；

   //将初始无序的R[1]到R[n]建成一个小根堆for(i = n/2;i >= 1; i--){    HeapAdjust(R, i, n);}

   由以上分析知：

   若对一无序序列建堆，然后输出根；重复该过程就可以由一个无需序列输出有序序列。快速排序

4. 选择排序：简单选择排序、

   然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。

稳定性：

快速排序是一种不稳定的排序算法。

另外，堆排序仅需个记录大小供交换用的辅助存储空间。

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

排序方法的分类

按数据存储介质：

内部排序和外部排序

内部排序：数据量不大、选择排序、

堆排序算法：

void HeadSort(elem R[]){    //R[1]到R[n]进行堆排序    int i;    for(i = n/2;i >= 1; i--)    {        HeapAdjust(R, i, n);//创建初始堆    }    for(i = n;i >= 1; i--)    {        Swap(R[1], R[i]);//根与最后一个元素交换        HeapAdjust(R, 1, i-1);//对R[1]到R[i-1]重新建堆    }}

算法性能分析

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。最后一个数、

4.归并排序

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

在内部排序中，通常采用的是2-路归并排序

即：将两个位置相邻的有序子序列R[L...m]和R[m+1...n]归并为一个有序序列R[l...n]

示例：

设初始关键字序列为[48 34 60 80 75 12 26 *48]

 整个归并排序仅需log2n趟

设R[low]-R[mid]和R[mid+1]-R[high]为相邻，归并成一个有序序列R1[low]-R1[high]。

基数排序：数字是有范围的，均由0~9十个数字组成，则只需要设置十个箱子，相继按照个十百千……进行排序。(基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制)。堆排序

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

基数排序

按排序所需工作量

1. 简单的排序方法：T(n)=O(n^2)

2. 基数排序：T(n)=O(d.n)

3. 先进的排序方法：T(n)=O(nlogn)

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

#define MAXSIZE 20 //设记录不超过20个typedef int KeyType; // 设关键字为整型量（int型）​Typedef struct{    //定义每一个记录（数据元素）的结构    KeyType key;//关键字    InfoType otherinfo;//其他数据项}RedType;//Record Type​Typedef struct{    //定义顺序表的结构    RedType r[MAXSIZE+1];//存储顺序表的向量    int length;//顺序表的长度}SqList;

2.插入排序

1.直接插入排序

基本操作：有序插入

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

提升快速排序

划分元素的选取是影响时间性能的关键

输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。

按稳定性：

稳定排序和非稳定排序

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

在插入a[i]前，数组a的前半段(a[0] ~ a[i-1])是有序断，后半段(a[i] ~ a[n-1])是停留在输入次序的“无序段”。信息量庞大，无法将整个文件复制进内存中进行排序。

如果内存可以容纳n个元素的话，那么平均每个子串的长度为2m，也就是说，使用置换选择算法我们可以减少一半的子串数。数据在外存(文件排序)

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

7.各类排序方法的综合比较

1.时间性能

1. 按平均的时间性能来分，有三类排序方法：

   时间复杂度为O(nlogn)的方法有：快速排序、

   再对(46,50,68,74,79,85,90)进行快速排序划分呢？

   由于每次枢轴记录的关键字都是大于其它所有记录的关键字，致使一次划分之后得到的子序列()的长度为0，这时已经退化成为没有改进措施的冒泡排序。

   目录

   1.基本概念和排序方法概述

   排序方法的分类

   2.插入排序

   1.直接插入排序

   2.折半插入排序

   3.希尔排序

   3.交换排序

   1.冒泡排序

   2.快速排序

   3.简单选择排序

   4.堆排序

   4.归并排序

   5.基数排序

   6.外部排序

   7.各类排序方法的综合比较

   1.时间性能

   2.空间性能

   3.排序方法的稳定性能

   4.关于“排序方法的时间复杂度的下限“

   ---

   

   1.基本概念和排序方法概述

   排序：将一组杂乱无章的数据按一定规律顺次排列起来。它包括两个相对独立的阶段：

   根据内存缓冲区大小，将外存上的文件分成若干长度为t的子文件，依次读入内存并利用内部排序方法对他们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串。右子树的根结点值进行比较，并与其中小者进行 交换；

2. 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的 调整过程为“筛选”

大根堆则排序方法相似。

快速排序不适于对原本有序或基本有序的记录序列进行排序。然后，逐一将a[1]至a[n-1]插入到有序子序列中。这正是此算法的缺点。数据在内存，无需内外存交换数据

外部排序：数据量较大、

当待排记录序列按关键关顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能退化为O(n2),因此是应该尽量避免的情况。因为磁盘读 / 写的机械动作所需的时间远远超过内存运算的时间（相对而言可以忽略不记），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。最中间一个数、若改用4路归并排序，则只需2趟排序，外部排序时的总读写次数便减少为96。

例子：

对49, 38, 20, 97, 76进行快速排序，先取定49作为分类中间数，左右两边进行排序

第一次：38, 20, 49, 97, 76

第二次：20, 38, 49, 76, 97

void QSort(SqList &L, int low, int high){    //对顺序表L快速排序    if(low < high)    {        //长度大于1        pivotloc = Partition(L, low, high);        //将L.r[low.high]一分为二，pivotloc为枢轴元素排好序的位置        QSort(L, low, pivotloc-1);//对低子表递归排序        QSort(L, pivotloc-1, high);//对高子表递归排序    }}​void Partition(SqList &L, int low, int high){    L.r[0] = L.r[low];    pivotkey = L.r[low].key;    while(low < high)    {        while(low < high && L.r[high].key >= pivotkey) --high;        L.r[low] = L.r[high];        while(low < high && L.r[low].key <= pivotkey) ++low;        L.r[high] = L.r[low];    }    L.r[low] = L.r[0];    return low;}​void main(){    QSort(L, 1, L.length);}

时间复杂度：

可以证明，平均计算时间是O(nlog2n)

1. Qsort():O(log2n)

2. Partition():O(n)

实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。

基本操作：

1. 首先通过n-1次关键字比较，从n个记泰中找出关键字最小的记录，将它与第一个记录交换

2. 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将 它与第二个记录交换

3. 重复上述操作，共进行-1趟排序后，排序结束

【算法】

void SelectSort(SqList &K){    for(i = 1;i < L.length; ++i)    {        k = i;        for(j = i+1;j <= length; j++)        {            if(L.r[j].key < L.r[k].key)                k = j;//记录最小值位置        }        if(k != i)        {            int temp = L.r[i];            L.r[i] = L.r[k];            L.r[k] = temp;        }    }}

时间复杂度

记录移动次数

1. 最好情况：0

2. 最坏情况：3(n-1)

比较次数：无论待排序列处于什么状态，选择排序所需进行的"比较”次数都相同

算法稳定性：

简单选择排序是不稳定排序

4.堆排序

堆的定义：

若n个元素的序列{a1 , a2 , …an}满足

ai ≤ a2i ai ≤ a2i+1 或者 ai ≥ a2i ai ≥ a2i+1

则分别称该序列{a1, a2, …an}为小根堆和大根堆。

改变分元素的选取方法，至多只能改变算法平均情况的下的世界性能，无法改变最坏情况下的时间性能。

可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法