数据结构_排序网站首页 技术杂谈

排序的确切定义如下：

输入：n 个记录 $R_{1}$ ， $R_{2}$ ， $R_{3}$ …… $R_{n}$ ，对应的关键字为 $k_{1}$ ， $k_{2}$ ，…… $k_{n}$ 。

输出：输入序列的一个重排 $R_{1}^{'}$ ， $R_{2}^{'}$ …… $R_{n}^{'}$ ，使得 $k_{1}^{'}$ $leq$ $k_{2}^{'}$ $leq$ …… $k_{n}^{'}$ (其中的 $leq$ 可以换成其他的比较大小的符号)。

算法的稳定性：若待排序表中有两个元素 $R_{i}$ 和 $R_{j}$ ，其对应的关键字相同即 $key_{i}$ = $key_{j}$ ，且在排序前 $R_{i}$ 在 $R_{j}$ 前面，若使用某一排序算法排序后， $R_{i}$ 仍在 $R_{j}$ 前面，则称这个排序算法是稳定的，否则称这个排序算法是不稳定的。需要注意的是：算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。

注意：对于不稳定的排序算法，只需举出一个关键字的实例，说明它的不稳定性即可。

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：①内部排序，是指在排序期间元素全部存放在内存中的排序；②外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。

内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般由比较和移动的次数决定。

这里拓展一个公式：

对于任意序列进行基于比较的排序，求最少的比较次数，应考虑在最坏的情况下。对任意 n 个关键字排序的比较次数至少为 log2(n!)向上取整；

log2(7!)=13；

2. 插入排序

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。

由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。

2.1 直接插入排序

假设在排序过程中，待排序表 L[1……n] 在某次排序过程中的某一时刻状态如下：

要将元素L（i）插入到已有序的子序列 L[1……i-1]，需要执行以下操作（为避免混淆，下面用 L[] 表示一个表，而用 L(）表示一个元素）

1. 查找 L(i) 在 L[1……i-1] 中的插入位置 k。

2. 将 L[k……i-1] 中的所有元素依次后移一个位置。

3. 将 L(i) 复制到 L(k)。

为了实现对 L[1……n] 的排序，可以将 L(2) ~ L(n) 依次插入前面已排好序的子序列，初始 L[1] 可以视为是一个已排好序的子序列。上述操作执行 n-1 次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为 O(1)），因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

//直接插入排序的代码

void InsertSort(ElemType A[],int n)
{
    int i,j;
    for(i=2;i<=n;i++)  //依次将A[2]~A[n] 插入前面已排序序列
    {
        if(A[i]<A[i-1])  // 若A[i]关键码小于其前驱，将A[i]插入有序表
        {
            A[0]=A[i];  //复制为哨兵，A[0] 不存放元素
            for(j=i-1;A[0]<A[j];--j) //从后往前查找待插入位置
                A[j+1]=A[j]; //向后挪位
            A[j+1]=A[0];  //复制到插入位置
        }
    }
}

假定初始序列为49, 38，65, 97 ,76, 13, 27, 49，初始时49#(也就是49取反的意思)可以视为一个已排好序的子序列

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1)。

时间效率：在排序过程中，向有序子表中逐个插入元素的操作进行了 n-1 趟，每趟操作都分为比较关键字和移动元素，比较次数和移动次数取决于待排序表的初始状态。

直接插入排序算法的时间复杂度为 O( $n^{2}$ )。

稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

注意：大部分排序算法都仅适用于顺序存储的线性表。

2.2 折半插入排序

折半插入排序实质上是在直接插入排序的基础上进行优化的一种排序。

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：①从前面的有序子表中查找出待插入元素应该被插入的位置；②给插入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是一边比较一边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。

//折半插入排序算法

void InsertSort(ElemType A[],int n)
{
    int i,j,loe,high,mid;
    for(i=2,i<=n;i++) //依次将A[2]~A[n]插入前面的已排序序列
    {
        A[0]=A[i]; //将A[i]暂存到A[0];
        low=1;   
        high=i-1;  //设置折半查找的范围
        while(low<=high) //折半查找，递增有序
        {
            mid=(low+high)/2; //取中间点
            if(A[mid]>A[0])
                high=mid-1; //查找左半子表
            else
                low=mid+1;  //查找右半子表
        }
        for(j=i-1;j>=high+1;--j)
        {
            A[j+1]=A[j];  //统一后移元素，空出插入位置
        }
        A[high+1]=A[0];   //插入操作
    }
}

从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为 O(nlog2n)，该比较次数与待排序表的初始状态无关，仅取决于表中元素个数 n；而元素的移动次数并未改变，它依赖于待排序表的初始状态。

因此，折半插入排序的时间复杂度仍是 O( $n^{2}$ )，对于数据量不是很大的排序表，折半查找排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

2.3 希尔排序

直接插入排序算法的时间复杂度为 O( $n^{2}$ )，但若待排序列为 “正序” 时，其时间复杂度可提高至 O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干形如 L[i，i+d，i+2d……i+kd] 的 “特殊” 子表，即把相隔某个 “增量” 的记录组成一个子表，对各子表分别进行直接插入排序，当整个表中的元素已呈 “基本有序” 时，再对全体记录进行一次直接插入排序。

希尔排序的过程如下：先取一个小于 n 的步长 $d_{1}$ ，把表中的全部记录分成 $d_{1}$ 组，所有距离为 $d_{1}$ 的倍数的记录放在同一组，在各组中进行直接插入排序；然后取第二个步长 $d_{2}$ < $d_{1}$ ，重复上述过程，直到所取到的 $d_{t}$ = 1，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，所以可以很快的得到最终结果。

第一趟取增量 $d_{1}$ = 5，将该序列分成 5 个子序列，即图中的第二行至第六行，分别对各子序列进行直接插入排序，结果如第七行所示；第二趟取增量 $d_{2}$ = 3，分别对 3 个子序列进行直接插入排序，结果如第 11 行所示；最后对整个序列进行一趟直接插入排序，整个排序过程如下图所示：

//希尔排序算法代码

void ShellSort(ElemType A[],int n)
{
    //A【0】只是暂存单元，不是哨兵，当j<=0 时，插入位置已到
    for(dk=n/2;dk>=1;dk=dk/2) //步长变化
    for(i=dk+1;i<=n;++i)
        if（A【i】<A【i-dk】）
            {//需将A【i】插入有序增量子表
                A[0]=A[i]; //暂存在A【0】
                for(j=i-dk;j>06&A[0]<A[j];j-=dk)
                    A[j+dk]=A[j]; //记录后移，查找插入的位置
                A[j+dk]=A[0]; //插入
            }
}

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1)。

时间效率：当 n 在某个特定范围内时，希尔排序的时间复杂度约为 O( $n^{1.3}$ )。在最坏情况下希尔排序的时间复杂度为 O( $n^{2}$ )。

稳定性：希尔排序是一种不稳定的排序方法。

适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

2.4 相关练习

3. 交换排序

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法有很多，我们这里着重学习冒泡排序和快速排序。

3.1 冒泡排序

冒泡排序的基本思想是：从后往前（或者从前往后）两两比较相邻元素的值，若为逆序（即A[i-1] > A[i]），则交换他们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上 “漂浮” 直至 “水面” （或关键字最大的元素如石头一般下沉至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到序列的最终位置……这样最多做 n-1 趟冒泡就能把所有元素排好序。

看下述例子中冒泡排序的过程：

第一趟冒泡时：27<49，不交换；13<27，不交换；76>13，交换；97>13，交换；65>13，交换；38>13，交换；49>13，交换。通过第一趟冒泡排序后，最小的元素已经交换到第一个位置，也是这个元素的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，以此类推，直到冒泡排序结束；

void BubbleSort(ElemType A[],int n)
{
    for(i=0;i<n-1;i++)
    {
        flag=false; //表示本趟冒泡是否发生交换的标志
        for(j=n-1;j>i;j--) //一趟冒泡排序
        {
            if(A[j-1]>A[j]) //若为逆序
            {
                swap(A[j-1],A[j]); //交换
                flag=true;
            }
        }
        if(flag==false)
            return; //本趟遍历后没有发生交换，说明表已经有序
    }
}

上述的算法是采用从后向前进行比较交换的；

//这里注意上述代码：
j的范围之所以是sz-1-i是因为 每冒泡排序一次 就会把最小的（或者最大的）放到最终序列对应的位置
下一次冒泡排序就不再需要比较这个确定的元素了；
所以说每次要减去已经确定的元素

还要注意：如果 j 初始是0；那么if判断语句只能是 j 和 j+1 进行比较；因为数组下标 0 之前是没有元素的

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1)。

时间效率：最好情况下的时间复杂度为 O(n)；最坏情况下的时间复杂度为 O( $n^{2}$ )，其平均时间复杂度为 O( $n^{2}$ )。

稳定性：冒泡排序是一种稳定的排序算法。

注意：

冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

3.2 快速排序

快速排序的基本思想是基于分治法的：在待排序表 L[1……n] 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分 L[1……k-1] 和 L[k+1……n]，使得 L[1……k-1] 中所有元素小于 pivot，L[k+1……n] 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L(k) 上，这个过程称为一趟快速排序（或一次划分）。然后分别递归的对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程。

下例中附设两个指针 i 和 j，初值分别为 low 和 high，取第一个元素 49 为枢轴赋值到变量 pivot。

void QuickSort(ElemType A[],int low,int high)
{
    if(low<high)  //递归跳出的条件
    {
        //Partition() 就是划分操作，将表A[low……high]划分为满足上述条件的两个子表
        int pivotpos=Partition(A,low,high);  //划分
        QuickSort(A,low,pivotpos-1); //依次对两个子表进行递归排序
        QuickSort(A,pivotpos+1,high);
    }
}
int Partition(ElemType A[],int low,int high) //一趟划分
{
    ElemType pivot=A[low];  //将当前表中第一个元素设为枢轴，对表进行划分
    while(low<high)
    {
        while(low<high && A[high]>=pivot)
        {
            --high;
        }
        A[low]=A[high]; //将比枢轴小的元素移动到左侧    
        while(low<high && A[low]<=pivot)
        {
            ++low;
        }
        A[high]=A[low]; //将比枢轴大的元素移动到右侧
    }
    A[low]=pivot; //枢轴元素存放到最终位置
    return low;   //返回存放枢轴的最终位置     
}

空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为O(log2n)；最坏情况下要进行 n-1 次递归调用，所以栈的深度为 O(n)；平均情况下，栈的深度为 O(log2n)；

时间效率：快速排序的运行时间与划分是否对称有关；最好的时间复杂度为 O( $n^{2}$ )；最坏的时间复杂度为 O(nlog2n)；平均时间复杂度为 O(nlog2n)；

快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性：快速排序是一种不稳定的排序方法。

注意：

在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上。

3.3 相关练习

4. 选择排序

选择排序的基本思想就是：每一趟（如第 i 趟）在后面 n - i + 1（i = 1,2,3,4,5……n-1）个待排序元素中选取关键字最小的元素，作为有序子序列的第 i 个元素，直到第 n-1 趟做完，待排序元素只剩下 1 个，就不用再选了。（定义可能比较抽象，具体举个例子来看：第一趟肯定是要处理序列中第一个元素，升序的前提下，n-1+1，也就是从 n 个元素里面选择一个最小的，作为序列中第一个元素；第二趟从 n-2+1=n-1，也就是从除第一趟处理过的元素之外，选择一个最小的元素，作为序列中第二个元素；以此类推，这样每一趟都能保证从待选序列中选择一个最小的，依次放到序列中）

4.1 简单选择序列

简单选择排序算法的思想是：假设排序表为 L[1……n]，第 i 趟排序即从 L[i……n] 中选择关键字最小的元素与 L(i) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 n-1 趟排序就可使得整个排序表有序。

//简单选择排序算法

void SelectSort(ElemType A[],int n)
{
    for(i=0;i<n-1;i++)  //一共进行 n-1 趟，每一趟确定一个最小元素的最终位置
    {
        min=i;  //记录最小元素位置
        for(j=i+1;j<n;j++)  //在 A[i……n-1]中选择最小的元素
        {
            if(A[j]<A[min]) //A[min]就是假设序列中的最小元素，如果发现序列中还有比这个更小的元素
                            //就更新最小值所在的位置
                min=j;   //更新最小元素的位置
            if(min!=i)
                swap(A[i],A[min]); // 交换最小值和 A[i] 之间的位置
        }
    }
}

空间效率：仅使用常数个辅助单元，故空间效率为 O(1)。

时间效率：元素间的比较的次数与序列的初始状态无关，始终是 n(n-1)/2 次，因此时间复杂度始终是 O( $n^{2}$ )。

稳定性：在第 i 趟找到最小元素后，和第 i 个元素交换，可能会导致第 i 个元素与其含有相同关键字元素的相对位置发生改变。因此，简单选择排序是一种不稳定的排序方法。

4.2 堆排序

堆的定义如下， n 个关键字序列 L[1……n] 称为堆，当且仅当该序列满足：

①：L(i) >= L(2i) 且 L(i) >= L(2i+1) 或

②：L(i) <= L(2i) 且 L(i) <= L(2i+1)

可以将该一维数组视为一棵完全二叉树，满足条件 ① 的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。满足条件 ② 的堆称为小根堆（小顶堆），小根堆的定义刚好相反，根结点是最小元素。

堆排序的思路是：首先将存放在 L[1……n] 中的 n 个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已经不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩下一个元素为止。

堆排序的关键是构造初始堆。n 个结点的完全二叉树，最后一个结点是第 n/2向下取整个结点的孩子。对第 n/2向下取整个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对各结点为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。（简单来说就是：对于大根堆，依次对各结点为根的子树进行判断，如果发现该子树中孩子结点的关键字值比父结点的值大，就取孩子结点中的较大值与父结点进行交换；重复筛选各个结点，但是需要注意，交换之后可能会破坏下一级的堆，所以需要多次重复）

上面的定义过于抽象，直接举例子如下图所示：

初始时调整 L(4) 子树，09<32，交换，交换后满足堆的定义；向前继续调整 L(3) 子树，78<左右孩子的较大值87，交换，交换后满足堆的定义；向前调整 L(2) 子树，17<左右孩子的较大值45，交换后满足堆的定义；向前调整至根结点 L(1)，53<左右孩子的较大值87，交换，交换后破坏了 L(3) 子树的堆，采用上述方法对 L(3) 进行调整，53<左右孩子的较大值87，交换，至此该完全二叉树满足堆的定义。

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将09和左右孩子的较大值78交换，交换后破坏了 L(3) 子树的堆，继续对 L(3) 子树向下筛选，将09和左右孩子的较大值65交换，交换后得到了新堆；

//建立大根堆的算法

void BuildMaxHeap(ElemType A[],int len)
{
    for(int i=len/2;i>0;i--) //反复调整堆
    {
        HeadAdjust(A,i,len); 
    }        
}
void HeadAdjust(ElemType A[],int k,int len)
{
    //函数HeadAdjust将元素 k 为根的子树进行调整
    A[0]=A[k];  //A[0]暂存子树的根结点
    for(i=2*k;i<=len;i=i*2) //沿key较大的子结点向下筛选
    //在学习树这一种数据结构时，我们知道子树的根结点为 i ，那么其左孩子就为 2i，右孩子就是 2i+1
    //这一步的for循环就是为了确定子树的左孩子和右孩子到底谁大，大的那个就要和根结点进行交换
    {
        if(i<len && A[i] < A[i+1]) //i一定要小于 len，i初始化为 2k，也就是左孩子
        {
            i++;  //取key较大的子结点的下标
        }
        if(A[0]>=A[i]) //拿左孩子和根结点进行比较，如果左孩子比根结点还要小，那么根结点就是最大的，break筛选结束；
            break;  //筛选结束
        else  //否则就意味着左孩子比根结点要大，那么左孩子就要和根结点进行互换
        {
            A[k]=A[i];  //将A[i]调整到双亲结点上
            k=i;  //修改 k 值，以便继续向下筛选
        }
    }
    A[k]=A[0];  //被筛选结点的值放入最终位置
}

//时间复杂度为O(n)。

//堆排序的算法

void HeapSort(ElemType A[],int len)
{
    BuildMaxHeap(A,len); //初始建堆
    for(i=len;i>1;i--)  // n-1 趟的交换的建堆过程 
    {
        Swap(A[i],A[1]); //输出堆顶元素（和堆底元素交换）
        HeadAdjust(A,1,i-1); //调整，把剩余的 i-1 个元素整理成堆
    }
}

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。

堆排序适合关键字较多的情况。例如，在一亿个数中选出前 100 个最大值？

首先使用一个大小为 100 的数组，读入前 100 个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。

空间效率：仅使用常数个辅助单元，所以空间复杂度为 O(1)。

时间效率：堆排序的时间复杂度为 O(nlog2n)。

稳定性：堆排序是一种不稳定的排序方法。

4.3 相关练习

5. 归并排序和基数排序

5.1 归并排序

归并排序与上述基于交换、选择等排序的思想不一样， “归并” 的含义是将两个或两个以上的有序表组合成一个新的有序表。

假定待排序表含有 n 个记录，则可将其视为 n 个有序的子表，每个子表的长度为 1 ，然后两两归并，得到 n/2向上取整个长度为2或1的有序表；继续两两归并……如此重复，直到合并成一个长度为 n 的有序表为止，这种排序方法称为 2 路归并排序。

在每一趟的过程中，既要考虑子表有序，又要考虑每个子表之间有序；

//2路归并排序算法

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));  //辅助数组B，将数组A中两个有序表复制到数组B中，在数组B中进行关键字的比较，较小者放入A中，
void Merge(ElemType A[],int low,int mid,int high)
{
    //表A的两段A[low……mid]和A[mid+1……high]各自有序，将它们合并成一个有序表
    for(int k=low;k<=high;k++)
    {
        B[k]=A[k]; //将A中所有元素复制到B中
    }
    for(i=low,j=mid+1,k=i;i<mid&&j<=high;k++)
    {
        if(B[i]<=B[j])  //比较B的左右两段中的元素
            A[k]=B[i++]; //将较小值复制到A中
        else
            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
    //当数组B中有一段的下标超过其对应的表长（即该段的所有元素都已经复制到A中）时，将另一段中的剩余部分直接复制到A中。
}

递归形式的2路归并算法是基于分治的，其过程如下。

分解：将含有 n 个元素的待排序表分成各含 n/2 个元素的子表，采用 2 路归并排序算法对两个子表递归地进行排序。

合并：合并两个已排序的子表得到排序结果。

void MergeSort(ElemType A[],int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;  //从中间划分两个子序列
        MergeSort(A,low,mid);  //对左侧子序列进行递归排序
        MergeSort(A,mid+1,high);  //对右侧子序列进行递归排序
        Merge(A,low,mid,high);  //归并
    }
}

C语言实现归并排序：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//归并排序：将一个数组中两个相邻有序空间合并成一个

//参数介绍
//arr  --  包含两个有序区间的数组
//low  --  第一个有序区间的起始地址
//mid  --  第一个有序区间的结束地址。同时也可以通过mid表示第二个有序区间的起始地址
//high  --  第二个有序区间的结束地址

void Merge(int arr[],int low,int mid,int high)
{
	int *temp = (int*)malloc((high - low + 1)*sizeof(arr));  //动态开辟可以存储arr的数组temp，用来存储归并排序后数组
	int i = low;
	int j = mid + 1;
	int k = 0;  //其中 i j k 分别表示第一个有序区间、第二个有序区间和动态开辟空间的索引指针
	while (i <= mid && j <= high)
	{
		if (arr[i] < arr[j])  //比较两个子序列中的元素，将较小的元素放到temp数组中
			temp[k++]=arr[i++];
		else
			temp[k++] = arr[j++];
	}
	while (i<=mid)
		temp[k++] = arr[i++];
	while (j <= mid)
		temp[k++] = arr[j++]; //就是说该数组不是正好对称的，分开的两个子序列的元素个数不相同，那么比较之后，必然有一个子序列先放进temp中；另外一个还剩余元素
	//以上两个while循环就是为了处理其中一个子序列剩下元素的情况
	//当数组temp中有一段的下标超过其表长（即该段的所有元素都已经复制到arr中）时，将另一段中的剩余部分直接复制到arr中；
	for (i = 0; i < k;i++)
	{
		arr[low + i] = temp[i];
	}
	free(temp);
	temp = NULL; //释放动态开辟的空间
}
void MergeSort(int arr[], int low, int high)
{
	if (arr == NULL || low >= high)
	{
		return;
	}
	int mid = (low + high) / 2;  //对中间划分两个子序列
	//接下来递归的对划分的左右两个子序列进行排序
	MergeSort(arr,low,mid);  //对左侧子序列进行递归排序
	MergeSort(arr, mid + 1, high);  //对右侧子序列进行递归排序
	Merge(arr,low,mid,high);  //归并
}
int main()
{
	int i = 0;
	int arr[] = { 2, 0, 1, 4, 5, 6, 8, 7, 3, 9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	MergeSort(arr,0,sz-1);
	for (i = 0; i < sz; i++)
		printf("%d ", arr[i]);
	printf("
");
	return 0;
}

空间效率：Merge()操作中，辅助空间刚好 n 个单元，所以算法的空间复杂度为 O(n)。

时间效率：每趟归并的时间复杂度为O(n)（每趟都要对n个元素进行排序），共需进行 log2n向上取整趟归并（归并的过程可以看做是一个完全二叉树，每一趟归并都要将2个孩子结点合并成父结点，所以归并的躺数可以看成是完全二叉树的高度，也就是 log2n），所以算法的时间复杂度为 O(nlog2n)。

稳定性：2 路归并排序算法是一种稳定的排序方法。

5.2 基数排序

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

假设长度为 n 的线性表中每个结点 $a_{j}$ 的关键字由 d 元组 ( $k_{j}^{d-1}$ ， $k_{j}^{d-2}$ ……， $k_{j}^{1}$ ， $k_{j}^{0}$ ) 组成，其中 $k_{j}^{d-1}$ 为最主位关键字， $k_{j}^{0}$ 为最次位关键字。

为实现多关键字排序，通常有两种方法：第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD）法，按关键字权重递减依次进行排序，最后形成一个有序序列。

        下面描述以 r 为基数的最低位优先基数排序的过程，在排序过程中，使用 r 个队列 $Q_{0}$ ， $Q_{1}$ …… $Q_{r-1}$ 。基数排序的过程如下：

        对 i = 0,1,2,3，……d-1，依次做一次 “分配” 和 “收集” （实际上是一次稳定的排序过程）。

分配：开始时，把   $Q_{0}$ ， $Q_{1}$ …… $Q_{r-1}$ 各个队列置成空队列，然后依次考察线性表中的每个结点 $a_{j}$ (j = 0,1，……n-1)，若 $a_{j}$ 的关键字 $k_{j}^{i}$ = k，就把 $a_{j}$ 放进 $Q_{k}$ 队列中。

收集：把   $Q_{0}$ ， $Q_{1}$ …… $Q_{r-1}$ 各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。

通常采用链式基数排序，假设对如下 10 个记录进行排序：

每个关键字是 1000 以下的正整数，基数 r = 10，在排序过程中需要借助 10 个链队列，每个关键字由 3 位子关键字构成 $K^{1}K^{2}K^{3}$ ，分别代表百位、十位和个位，一共需要进行三趟 “分配” 和 “收集” 操作。第一趟分配用最低位子关键字 $K^{3}$ 进行，将所有最低位子关键字（个位）相等的记录分配到同一个队列，然后进行收集操作。

第二趟分配用次低位关键字 $K^{2}$ 进行，将所有次低位子关键字（十位）相等的记录分配到同一个队列，然后进行第二趟收集。注意：第二趟的分配是建立在第一趟收集的基础之上的；

第三趟分配用最高位子关键字 $K^{1}$ 进行，将所有最高位子关键字（百位）相等的记录分配到同一个队列，然后进行第三趟收集；至此：整个排序结束；

空间效率：一趟排序需要的辅助存储空间为 r （r 个队列：r 个队头指针和 r 个队尾指针），但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为 O(r)。

时间效率：基数排序需要进行 d 趟分配和收集，一趟分配需要 O(n)，一趟收集需要 O(r)，所以基数排序的时间复杂度为 O(d(n+r))，它与序列的初始状态无关。

稳定性：基数排序是一种稳定的排序；

5.3 相关练习

6. 各种内部排序算法的比较

从时间复杂度来看：简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为 O( $n^{2}$ )，实现过程也比较简单，但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O(n)，而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前仍未得到其精确的渐进时间。堆排序利用一种称为堆的数据结构，可在线性时间内完成建堆，且在 O(nlog2n) 内完成排序过程。快速排序基于分治的思想，虽然最坏情况下快速排序时间会达到 O( $n^{2}$ )，但快速排序的平均性能可以达到 O(nlog2n)，在实际应用中常常优于其他排序算法。归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为 O(nlog2n)。

从空间复杂度来看：简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间。快速排序在空间上只使用一个小的辅助栈，用于实现递归，平均情况下大小为 O(log2n)，当然在最坏情况下可能会增长到 O(n)。2路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为 O(n)；

从稳定性来看：插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。

7. 外部排序

7.1 外部排序的基本概念

之前学习过的都是在内存中进行的（称为内部排序）。而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序，在排序过程中需要多次进行内存和外存之间交换。这种排序方法就称为外部排序。

7.2 外部排序的方法

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间(相比而言可以忽略不计)，因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。

外部排序通常采用归并排序法。它包括两个相对独立的阶段：①根据内存缓冲区大小，将外存上的文件分成若干长度为 £ 的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串；② 对这些归并段进行逐趟归并，使归并段(有序子文件)逐渐由小到大，直至得到整个有序文件为止。

例如：

一个含有2000个记录的文件，每个磁盘块可容纳125个记录，首先通过8次内部排序得到8个初始归并段R1~R8，每个段含有250个记录。然后对该文件做两两归并，直至得到一个有序文件。

把内存工作区等分为3个缓冲区，如下图8.12 所示，其中两个为输入缓冲区，一个为输出缓冲区。

将两个输入归并段R1和R2分别读入一个块，放在输入缓冲区1和输入缓冲区2中。然后，在内存中进行两路归并，归并后的对象顺序存放在输出缓冲区中。若输出缓冲区中对象存满，则将其顺序写到输出归并段( $R1^{'}$ )中，再清空输出缓冲区，继续存放归并后的对象。若某个输入缓冲区中的对象取空，则从对应的输入归并段中再读取下一块，继续参加归并。如此继续，直到两个输入归并段中的对象全部读入内存并都归并完成为止。当R1和R2归并完后，再归并R3和R4、R5和R6、最后归并R7和R8，这是一趟归并。再把上趟的结果 $R1^{'}$ 和 $R2^{'}$ 、 $R3^{'}$ 和 $R4^{'}$ 两两归并，这又是一趟归并。最后把 $R1^{''}$ 和 $R2^{''}$ 两个归并段合并，结果得到最终的有序文件，一共进行了3趟归并。

在外部归并中实现两两归并时，由于不可能将两个有序段及归并结果同时存放在内存中，因此需要不停的将数据读出、写入磁盘，这将会耗费大量的时间。

外部排序的总时间 = 内部排序所需的时间 + 外存信息读写的时间 + 内部归并所需的时间

显然，外存信息读写的时间远远大于内部排序和内部归并的时间，因此应着力减少 I/O 次数。由于外存信息的读/写是以 “磁盘块” 为单位的，可知每一趟归并需进行 16 次 “读” 和 16 次 “写” ，3趟归并加上内部排序时所需进行的读/写，共需进行32*3+32=128；

若改用4路归并排序，则只需2趟归并，外部排序时的总读/写次数便减至32*2 + 32 = 96。因此，增大归并路数，可减少归并趟数，进而减少总的磁盘I/O次数。

7.3 多路平衡归并与败者树

首先，通过上节的学习可以发现增加归并路数 k 能减少归并躺数 S，进而减少 I/O 次数。然后，增加归并路数 k 时，内部归并的时间将增加。做内部归并时，在 k 个元素中选择关键字最小的记录需要比较 k-1 次，每趟归并 n 个元素需要做 (n-1)(k-1) 次比较，S 趟归并总共需要的比较次数为

显然，式中的内部归并时间是随着 k 值的增加而增加的。这将抵消由于增加 k 而减少外存访问次数所得到的收益。

为了使内部归并不受 k 的增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。 k 个叶子结点分别存放 k 个归并段在归并过程中当前参加比较的记录，内部结点用来记录左右子树中的 “失败者” ，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

采用败者树总的比较次数为

可见，使用败者树后，内部归并的比较次数与 k 无关了。因此，只要内存空间允许，增大归并路数 k 将有效减少归并树的高度，从而减少 I/O 次数，提高外部排序的速度。

7.4 置换 - 选择排序（生成初始归并段）

设初始待排文件为 FI，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 w 个记录。置换 - 选择算法的步骤如下：

从 FI 输入 w 个记录到工作区 WA。
从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录。
将 MINIMAX 记录输出到 FO 中去。
若 FI 不空，则从 FI 输入下一个记录到 WA 中。
从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录。
重复 3~5 ，直至在 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到 FO 中去。
重复 2~6 ，直至 WA 为空。由此得到全部初始归并段。

比方说：

设待排文件 FI = {17,21,05,44,10,12,56,32,29}，WA 容量为 3。

7.5 最佳归并树

文件经过置换 - 选择排序后，得到的是长度不等的初始归并段。

接下来谈论如何组织长度不等的初始归并段的归并顺序，使得 I/O 次数最少？假设由置换 - 选择得到 9 个初始归并段，其长度（记录数）依次为9,30,12,18,3,17,2,6,24。现做三路平衡归并。

图中，叶结点表示一个初始归并段，上面的权值表示该归并段的长度，叶结点到根的路径长度表示其参加归并的趟数，各非叶结点代表归并成的新归并段，根结点表示最终生成的归并段。树的带权路径长度 WPL 为归并过程中的总读记录数，故 I/O 次数 = 2 * WPL = 484.

显然，归并方案不同，所得的归并树也不同，树的带权路径长度（I/O次数）也不同。为了优化归并树的 WPL，将哈夫曼树的思想引入至此：在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的I/O次数最少的最佳归并树。

注意：

上图中的哈夫曼树是一棵严格的三叉树，即树中只有度为3或者度为0的结点；

倘若只有8个初始归并段，这样就导致最后一次做的是两路归并，而不再是三路归并了；倘若初始归并段不足以构成一棵严格的 k 叉树时，需添加长度为 0 的 “虚段”，也就是权值为 0 的结点，按照哈夫曼树的原则，权值为 0 的叶子应该离树根最远。