合并排序的算法思想

‘壹’ 归并排序的算法原理是什么

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。
归并排序基本原理

通过对若干个有序结点序列的归并来实现排序。
所谓归并是指将若干个已排好序的部分合并成一个有序的部分。

归并排序基本思想

设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。

在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。

‘贰’ 数据结构--归并排序与基数排序

一、归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。将两个或以上的有序表组合成一个新的有序表。
1、2-路归并排序
初始序列含有n个记录，可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列，再两两归并，如此重复，直至得到一个长度为n的有序序列为止。
2、举例

上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，实现步骤：

Tips：
排序算法的稳定性：保证排序前2个相等的数，在序列中的前后位置顺序和排序后它们两个的前后位置顺序相同。例如，Ai = Aj，Ai排序前位于Aj的前面，排序后Ai还位于Aj的前面。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。
排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成r[j]>=r[j+1]，则两个相等的记录就会交换位置，从而变成不稳定的算法。

堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

一、基数排序
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
1、什么是多关键字
已知扑克牌中52张牌面的次序关系为：

1、最高位优先于最低位优先

假设有n个记录的序列{R ₁ ，R ₂ ，...R _n }，且每个记录R _i 中含有d个关键字(K _i ¹ ，K _i ² ，...，K _i ^d )，序列{R ₁ ，R ₂ ，...R _n }对关键字(K ¹ ，K ² ，...，K ^d )有序是指：对于序列中任意两个记录R _i 和R _j (1 <= i < j <= n)都满足下列有序关系：(K _i ¹ ，K _i ² ，...，K _i ^d )<(K _j ¹ ，K _j ² ，...，K _j ^d )，其中K ¹ 称为最高位关键字，K ^d 称为最低位关键字。

实现多关键字排序的方法：
A、先对最高位关键字K ¹ 进行排序，间序列分成若干子序列，每个子序列中的记录都具有相同的K ¹ 值，然后分别对每个子序列对关键字K ² 进行排序，按K ² 值不同再分成若干更小的子序列，依次重复，直到对K ^d-1 进行排序后得到的每一子序列中的记录都具有相同的关键字(K ¹ ，K ² ，...，K ^d-1 )，而后每个子序列分别对K ^d 进行排序，最后将所要子序列依次连接在一起成为一个有序序列，这种方法为“最高位优先(MSD)”
B、先从最低位关键字K ^d 进行排序，在对高一位的关键字K ^d-1 进行排序，依次重复，直至对K ¹ 进行排序后便成为一个有序序列。这种方法称为“最低位优先(LSD)”。

三、内部排序方法的比较

结论：
1、表中的“简单排序”指：除希尔排序外的所有插入排序，冒泡排序和简单选择排序，其中之间插入排序最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将他和其他排序方法（快排，归并排序）结合在一起使用。
2、从平均时间性能看，快排最省时间，但他在最坏情况下的时间性能不如堆排序和归并排序。在n较大，归并排序所需时间比堆排序少，但所需的辅助存储量最多。
3、基数排序适用于n值很大且关键字较小的序列。

‘叁’ 排序算法总结

排序算法是什么?有多少种?排序算法总结又是怎样?以下是为您整理的排序算法总结，供您参考!

【排序算法总结】

排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。

排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。

稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。

以下来总结常用的排序算法，加深对排序的理解。

冒泡排序

原理

俩俩比较相邻记录的排序码，若发生逆序，则交旅派配换;有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。

优化

若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。

代码

插入排序

原理

依次选择一个待排序的数据，插入到前边已排好序的序列中。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。

优化

直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。

折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。

使用场景

当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

代码

希尔排拆指序

原理

插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：

插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。

但插入排序在每次往前插入时只能将数据移动一位，效率比较低。

所以希尔排序的思想是：

先是取一个合适的gap

缩小间隔gap，例如去gap=ceil(gap/2)，重复上述子序列划分和排序

直到，最后gap=1时，将所有元素放在同一个序列中进行插入排序为止。

性能

开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点;其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

代码

选择排序

原理

每次从未排序的序列中找到最小值，记录并最后存放到已排序序羡碰列的末尾

性能

时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的(把最小值交换到已排序的末尾导致的)，每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。

代码

快速排序

原理

分而治之思想：

Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1…q]，左边的元素都比基准小，右边的元素都比基准大;

Conquer：对俩个划分的数组进行递归排序;

Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。

性能

快排的平均时间复杂度为O(NlogN)，空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N);且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。

优化

当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。

所以快排的优化思路如下：

优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。

在规模较小情况下，采用直接插入排序

代码

归并排序

原理

分而治之思想：

Divide：将n个元素平均划分为各含n/2个元素的子序列;

Conquer：递归的解决俩个规模为n/2的子问题;

Combine：合并俩个已排序的子序列。

性能

时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。

优化

优化思路：

在规模较小时，合并排序可采用直接插入;

在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。

代码

堆排序

原理

堆的性质：

是一棵完全二叉树

每个节点的值都大于或等于其子节点的值，为最大堆;反之为最小堆。

堆排序思想：

将待排序的序列构造成一个最大堆，此时序列的最大值为根节点

依次将根节点与待排序序列的最后一个元素交换

再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

性能

时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。

使用场景

想知道最大值或最小值时，比如优先级队列，作业调度等场景。

代码

计数排序

原理

先把每个元素的出现次数算出来，然后算出该元素所在最终排好序列中的绝对位置(最终位置)，再依次把初始序列中的元素，根据该元素所在最终的绝对位置移到排序数组中。

性能

时间复杂度为O(N+K)，空间复杂度为O(N+K)，算法是稳定的，与初始序列无关，不需要进行比较就能排好序的算法。

使用场景

算法只能使用在已知序列中的元素在0-k之间，且要求排序的复杂度在线性效率上。

代码

桶排序

原理

根据待排序列元素的大小范围，均匀独立的划分M个桶

将N个输入元素分布到各个桶中去

再对各个桶中的元素进行排序

此时再按次序把各桶中的元素列出来即是已排序好的。

性能

时间复杂度为O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空间复杂度为O(N+M)，算法是稳定的，且与初始序列无关。

使用场景

算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中;可应用于数据量分布比较均匀，或比较侧重于区间数量时。

基数排序

原理

对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

性能

时间复杂度为O(d*(N+K))，空间复杂度为O(N+K)。

总结

以上排序算法的时间、空间与稳定性的总结如下：

‘肆’ 归并排序算法是什么

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置。

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。

重复步骤3直到某一指针超出序列尾。

将另一序列剩下的所有元素直接复制到合并序列尾。

‘伍’ 归并排序算法：用两路归并算法，实现N个无素的排序

合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。

例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示：

初始值 [49] [38] [65] [97] [76] [13] [27]

看成由长度为1的7个子序列组成

第一次合并之后 [38 49] [65 97] [13 76] [27]

看成由长度为1或2的4个子序列组成

第二次合并之后 [38 49 65 97] [13 27 76]

看成由长度为4或3的2个子序列组成

第三次合并之后 [13 27 38 49 65 76 97]

合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。
其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)

归并算法如下：
long merge(long *A,long p,long q,long r)
{
long n1,n2,i,j,k;
long *L,*R;
n1=q-p+1;
n2=r-q;
L=(long *)malloc((n1+2)*sizeof(long));
R=(long *)malloc((n2+2)*sizeof(long));
for(i=1;i<=n1;i++)
L=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=R[n2+1]=RAND_MAX;
i=j=1;
for(k=p;k<=r;k++)
{
if(L<=R[j])
{
A[k]=L;
i++;
}
else
{
A[k]=R[j];
j++;
}
}
free(L);
free(R);
return 0;
}

long mergesort(long *A,long p,long r)
{
long q;
if(p<r)
{
q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
return 0;
}