原理:
1、算法基本思路
设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。
(1)合并过程
合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。
(2)动态申请R1
实现时,R1是动态申请的,因为申请的空间可能很大,故须加入申请空间是否成功的处理。
实现:
//将分组a[low]..a[i]和分组a[i + 1]..a[high]合并
private static void merge(int[] a, int pivotPos, int low, int high)
{
int[] b = new int[a.length];
int p = low;
int q = pivotPos + 1;
int r = low;
while( p <= pivotPos && q <= high )
{
while( p <= pivotPos )
{
if( a[p] <= a[q] )
b[r++] = a[p++];
else
break;
}
while( q <= high )
{
if( a[q] < a[p] )
b[r++] = a[q++];
else
break;
}
}
while( p <= pivotPos )
b[r++] = a[p++];
while( q <= high )
b[r++] = a[q++];
for( int i = low; i <= high; i++)
a[i] = b[i];
}
//归并排序
//分治策略
//实践复杂度无论最好、平均都为O(nlogn)
//空间复杂度:O(n),一个额外的数组
public static void mergeSort(int[] a, int low, int high)
{
if ( low >= high )
return;
int pivotPos = (low + high) / 2;
mergeSort(a, low, pivotPos);
mergeSort(a, pivotPos + 1, high);
merge(a, pivotPos, low, high);
}
复杂度:
最好,最坏,平均都为O(nlogn)
空间复杂度: O(n),因为使用了一个额外的数组
稳定性:归并排序是稳定排序
相关推荐
本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...
归并排序(Merge Sort)是一种基于分治策略的高效排序算法,它的主要思想是将大问题分解成小问题,然后逐个解决小问题,最后再将解决好的小问题合并成解决大问题的答案。这种算法在计算机科学中有着广泛的应用,尤其...
### 分治策略与归并排序 #### 一、分治策略概述 在计算机科学领域,分治(Divide and Conquer)是一种非常重要的算法设计思想。它的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子...
归并排序
本文将对快速排序、归并排序、堆排序等常见排序算法进行比较和分析,探讨它们的优缺点和适用场景。 首先, let's 看一下这些排序算法的时间复杂度和空间复杂度: | 排序算法 | 平均情况 | 最好情况 | 最坏情况 | ...
在提供的"算法-理论基础- 排序- 归并排序(包含源程序).pdf"文件中,可能会包含以下内容: 1. 归并排序的详细步骤解释,包括伪代码或流程图。 2. 归并排序的源代码实现,可能是C++、Java、Python或其他编程语言。 ...
6. 归并排序(Merge Sort):归并排序也是基于分治策略,将大数组分成两个小数组,分别排序后再合并。无论数据如何,归并排序的时间复杂度始终保持为O(n log n)。 7. 基数排序(Radix Sort):基数排序是一种非比较...
排序-6-二路归并.cpp
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
归并排序-flash演 可自己输入数据..........
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
15-归并排序.cpp
**三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...
归并排序是一种高效的排序算法,基于“分治”策略。分治法是计算机科学中一种常用的解决问题的方法,它将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子...
Java常用排序算法-归并排序 归并排序是一种分治思想的排序算法,其基本思想是将待排序的数组分成若干个子序列,每个子序列都是有序的,然后再将子序列合并成一个有序的数组。这种算法的时间复杂度为O(n log n),...
本实验旨在通过对两种经典排序算法——快速排序和归并排序的研究与实现,深入理解它们的基本原理、时间复杂度,并通过编程实践比较这两种算法在不同数据规模下的性能表现。 #### 二、快速排序 **1. 基本思想** ...
算法的实现----归并排序 数据结构中学过的 编起耍哈哈
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序...合并排序也叫归并排序。