归并算法与分而治之

❶ 数据结构--归并排序与基数排序

一、归并排序
归并排序（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值很大且关键字较小的序列。

❷ 归并排序算法是什么

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

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

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

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

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

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

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

❸ 分治算法几个经典例子

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础。

图二

大整数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循环赛日程表

汉诺塔

❹ 基于比较的排序算法

    基于比较的排序算法，应该是最符合人们直觉的方法。在各种算法的技术书上，已经证明了基于比较的排序算法的时间最优复杂度为O(nlogn)。

    下面是几种常见的基于比较的排序算法：

    1. 选择排序：这应该是最直观的排序方法。在排序n个元素时，第一次遍历，找到最小的元素，将其与第一个元素互换；第二次遍历，找到次小的元素，将其与第二个元素交换；直至剩下最后一个元素。

    2. 冒泡排序：这应该是我们学到的第一种排序算法。基本思想就是，通过依次比较相邻的两个元素，如后值比前值小，则交换这两个值，小值被交换到前面，大值被交换到后面。这样一次遍历后，最大值被放到最后。而小值被交换到n-1前。然后再次遍历前n-1，n-2，直至最后2个元素。整个儿过程，小值随着不断的遍历过程，逐渐被交换到前面，很像气泡逐渐从水底逐渐冒出。所以被称为冒泡算法。

    3. 插入排序：这个算法的思想很直观。按照《算法导论》中的解释，这个算法可以参照我们平时打扑克的情形。当抓取一张牌的时候，按顺序比较手牌，将其插入到恰当的位置。这样保证了手中所有的牌依然有序。当已排序的值数量较多时，由于已经保证了有序，那么在确定新值插入位置的时候，可以通过二分查找的方法来去确定插入位置。

    4. 希尔排序：在冒泡算法中，所以小值只能以步长为1的速度向前面移动。希尔排序在步长上作了优化，开始以一个较大的m步长进行分组，每组进行插入排序，这样就实现了步长为m的移动。然后逐渐缩小步长m直至1。所以根本思想是尽可能的将元素移动较远的位置代替移动一位。

5.归并排序：该思想利用的是解决问题的一个常用思想，divide-and-conquer，即分而治之的思想。将n个元素每次2分，变为两个n/2个元素组，直至1个元素——1个元素，自然是排好序了。然后，再两两合并元素组，最终合并为一个元素组。归并算法，因为需要归并，所以必然需要一个额外的n空间来实现归并。

    6.快速排序：同样是分而治之的思想，将原始数据分为2组。但是与归并算法直接将原始数据分为两部分不同的是，快排选择一个中值，新的两个子组，一个子组所有的元素都小于中值，另外一个子组所有的元素都大于等于中值，直至元素个数为1。当元素个数为1时，实际上快排已经完成了排序。这点与归并排序也不同，快排在子组完成以后，无需额外的操作。很明显，快排的效率依赖于中值的选择。如果中值可以将数据分为两个数量相等的子组，那么效率则为最高的。快排无需额外的存储空间，可以in-place进行排序。

    7.堆排序：该思想是将原始元素视为一个平衡二叉树。然后要求父节点必须大于子节点的规则，调整该平衡二叉树。由于是平衡二叉树，所以数据被完美的等分。这样根节点即为最大值。这时，堆排序完成了最大值的选择。为排序，则将根节点与最后一个子节点交换。此时，树的规则被破坏，需要从根节点逐级verify规则。