假定有一个数组 A[1...n],low, middle, high 为它的三个索引,并有 1 ≤ low ≤ middle < high ≤ n,使得两个子数组 A[low...middle],A[middle+1...high] 各自按升序排列。
我们要重新排列A中元素的位置,使得 A[low...high] 中的元素也按升序排列。这就是合并 A[low...middle] 和 A[middle+1...high] 的过程。
举个例子,就是我们有个数组 A = { 0, 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 }; 这里 low=0, middle=5, high=10
我们要对它进行排序使 A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
我们可以使用这样的方法来合并这两个子数组:
首先使用两个索引 s 和 t,初始化时各自指向 A[low] 和 A[middle+1],再用一个空数组 B[low...high] 做暂存器。每一次比较元素 A[s] 和 A[t],将小的元素添加到辅助数组 B,如果相同就把 A[s] 添加进去。
然后更新索引,如果 A[s] ≤ A[t],则 s 加 1,否则 t 加 1,当条件 s=middle+1 或 t=high+1 成立时过程结束。
s=middle+1 时,我们把数组 A[t...high] 中剩余的元素添加到 B,
t=high+1 时,把数组 A[s...middle] 中剩余的元素添加到 B。
最后,把数组 B[low...high] 复制回 A[low...high]。
过程 Merge
输入 数组 A[1...n] 和它的三个索引 low, middle, high, 1 ≤ low ≤ middle < high ≤ n,
两个子数组 A[low...middle] 和 A[middle+1...high] 各自按升序排列
输出 合并两个子数组 A[low...middle] 和 A[middle+1...high] 的数组 A[low...high]
算法描述
comment: B[low...high] 是个辅助数组
s ← low; t ← middle+1; index ← low
while s ≤ middle and t ≤ high
if A[s] ≤ A[t] then
B[k] ← A[s]
s ← s + 1
else
B[k] ← A[t]
t ← t + 1
end if
index ← index + 1
end while
if s = middle+1 then B[k...high] ← A[t...high]
else B[k...high] ← A[s...middle]
end if
A[low...high] ← B[low...high]
以下是此算法的 Java 实现:
private static void merge(int[] array, int low, int middle, int high)
{
int length = high - low + 1;
int indexLowToMiddle = low; // 从 low 位置开始的索引
int indexMiddleToHigh = middle + 1; // 从 middle+1 位置开始的索引
int[] tempArray = new int[length];
int tempIndex = 0;
while (indexLowToMiddle <= middle && indexMiddleToHigh <= high)
{
if (array[indexLowToMiddle] <= array[indexMiddleToHigh])
{
tempArray[tempIndex] = array[indexLowToMiddle];
indexLowToMiddle += 1;
}
else
{
tempArray[tempIndex] = array[indexMiddleToHigh];
indexMiddleToHigh += 1;
}
tempIndex += 1;
}
if (indexLowToMiddle == middle + 1)
{
System.arraycopy(
array, indexMiddleToHigh, tempArray, tempIndex, length - tempIndex);
}
else
{
System.arraycopy(
array, indexLowToMiddle, tempArray, tempIndex, length - tempIndex);
}
System.arraycopy(tempArray, 0, array, low, length);
}
分享到:
相关推荐
合并算法排序即属于分治方法。合并(Merge)就是将两个或多个有序表合并成一个有序表,例如下图所示的两个有序表经合并运算后得到一个有序表。我们在此只用到两个有序表的合并,称为二路并〔Two-way merge)。
采用递归分治方法进行合并排序的算法下载 这是为上机做准备时写的
归并排序的实现过程可以分为两个步骤:分治和合并。在分治过程中,将待排序的序列不断地分成两个子序列,直到每个子序列只有一个元素为止。在合并过程中,将两个有序的子序列合并成一个有序的序列,直到最终得到一...
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法...
合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并,得到完全有序的序列;即先使每...
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法...
要求:理解分治法的算法思想,清楚两路合并排序和快速排序算法的基本原理和实施过程,能将输入的一组无序序列排列为有序序列后输出。比较不同排序算法的时间/空间复杂度和改进方法。 动态规划法 内容:用动态规划法...
归并排序是一种经典的分治思想的排序算法,它基于“分而治之”的策略,将待排序序列不断地二分,并对两个子序列分别进行递归排序,最终合并两个有序序列。由于其时间复杂度稳定在 O(nlogn) 级别,归并排序被称为算法...
实验目的:掌握使用分治策略消除...问题描述:合并排序(MERGE SORT),是用分之策略实现对n个元素进行排序的算法。合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 归并排序是建立在归并操作上的一种有效的...
(3)回溯时合并子问题的解,在两个子问题的解中大者取大,小者取小,即合并为当前问题的解。 归并排序的过程是,将数组分为许多的组,即将数组元素多的数组分为数组元素少的数组,然后再将其合并。它的优点是,...
# 分别对左右两个列表进行处理,分别返回两个排序好的列表 left = mergesort(seq[:mid]) right = mergesort(seq[mid:]) return merging(left, right) # 对排序好的两个列表合并,产生一个新的排序
该算法的核心在于合并两个有序数组的操作,通过比较两个数组中的元素,将它们按顺序放入一个新的数组中,从而完成合并。归并排序的时间复杂度为O(nlogn),是一种稳定的排序算法,适用于各种规模的数据集。在Java实现...
将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表。 排序过程如图: 代码如下: #include stdio.h #...
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
其基本模式如下: ... 分解:把合并排序分解成与两个子问题 伪代码: MERGE_SORT(A, begin, end) if begin < end then mid<- int((begin + end)/2) MERGE_SORT(A, begin, mid)
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置 第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并...
算法包括:顺序比较算法、空间换时间的改进算法、分治策略的改进算法。 1.顺序比较算法的核心思想是遍历两次数组A,第一次找到最大值及其位置,第二次找到第二大...在分治策略中,通常包含三个步骤:分解、解决和合并。
Step 3:合并两个已排序好的序列 易知,MS的关键在于Merge过程。对于这一过程的理解,算法导论中给出了一个形象的模型。 即假设桌面上有两堆已排序好的的牌,且每一堆都正面朝下放置。然后我们分别从两堆牌中选取...
归并排序的实现过程包括分解和合并两个主要步骤:分解是将数组不断分割成更小的子数组,直到每个子数组只包含一个元素;合并则是将两个已排序的子数组合并成一个新的有序数组。归并排序具有稳定性好、时间复杂度低...