归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
下图就是2-路归并排序的一个例子:
代价分析:
上图可以看出,一个N关键字的序列,两两归并可以构造一棵高度为[logN]的归并排序树。而每一次归并的时间复杂度为O(m+n)。因此每一趟归并的时间复杂度为O(N),如上图。归并排序算法的总时间复杂度为O(N*logN)
。其所需要的辅助空间就是一个能容纳中间合并结果的数量为N的连续空间。因此空间复杂度为O(N)
。是稳定排序方法。
速度仅次于快速排序。
------------------------------------------------------------------------------------------------
参考资料:
-------------------------------------------------------------------------------------------------------------------
我们可以用分治的思想解决归并排序,给定一个有N个关键字的有序序列,分治法的步骤如下:
(1)划分: 如果S中有1个元素,则直接返回S,因为它已经有序了。否则(S中至少有两个元素),把它们分别放入两个序列S1和S2中,S1和S2各包含大约S中的一半元素,即S1包含S中的前[N/2]个元素,S2包含S中的后[N/2]个元素。
(2)递归:递归求解子问题S1和S2。
(3)求解:归并有序序列S1和S2,使得他们成为一个有序序列,将其中的元素放回S中。
*这里有个问题就是排序的数字序列必须是2的次幂,否则就要处理越出的部分。
-------------------------------------------------------------------------------------------------------------------
public static void MergeSort(int[] array){
int size = array.length;
int step=2; // 设定一个步长
for(; step<=size; step*=2){ // 步长每次以2的指数级增长
for(int i=0; i<size; i+=step){
if(i+step<=size){
MergeSort(array, i, i+step/2-1, i+step-1);
}
}
}
// 对越出的部分(非2的次幂)进行处理
int lost = size%(step/2);
if(lost!=0){
MergeSort(array, 0, size-lost-1, size-1);
}
}
/**
* 对有序的子序列进行整合
* @param array
* @param start
* @param mid
* @param end
*/
private static void MergeSort(int[] array, int start, int mid, int end){
int i=start;
int j=mid+1;
int index = 0;
// 分配一个新的空间作为临时储存
int[] temp = new int[end-start+1];
// 对有序列进行排序
while(i<=mid && j<=end){
temp[index++] = array[i]<array[j]?array[i++]:array[j++];
}
while(i<=mid){
temp[index++] = array[i++];
}
while(j<=end){
temp[index++] = array[j++];
}
// 数据转移
index = 0;
for(int k=start; k<=end; k++){
array[k] = temp[index++];
}
}
- 大小: 36.9 KB
分享到:
相关推荐
归并排序 归并排序 归并排序 归并排序 归并排序
归并排序(Mergesort)是一种经典的排序算法,它基于分治法(Divide and Conquer)的设计理念。在C++中实现归并排序,我们可以遵循以下步骤: 1. **理解分治法**:分治法是将一个大问题分解成若干个规模较小的相同...
### 分治策略与归并排序 #### 一、分治策略概述 在计算机科学领域,分治(Divide and Conquer)是一种非常重要的算法设计思想。它的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子...
归并排序(Merge Sort)是一种基于分治策略的高效排序算法。它的基本思想是将待排序的元素序列分成两个或更多的子序列,分别对每个子序列进行排序,然后将排好序的子序列合并成一个有序序列。这个过程可以递归进行,...
归并排序是一种高效的排序算法,基于“分治”策略。它的基本思想是将大问题分解成小问题,分别解决后再合并结果。在C语言中实现归并排序,我们需要理解其核心步骤并用适当的编程语法来表达。 首先,归并排序分为两...
代码是归并排序的c语言实现,归并算法MergeSortList.cpp
在这个代码示例中,`mergeSort`函数是归并排序的主体,它首先检查子数组的大小,如果子数组只有一个元素,则不需要再进行排序。否则,它会递归地对左右两个子数组进行排序,最后调用`merge`函数将结果合并。 归并...
归并排序是一种高效的排序算法,基于分治策略。在C语言中实现归并排序,我们需要理解其基本原理和步骤,然后编写相应的代码。下面将详细解释归并排序的原理、步骤以及C语言实现的关键点。 **归并排序原理:** 归并...
**三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...
在上述代码中,`mergeSort()` 函数实现了归并排序的递归过程,`merge()` 函数负责合并两个子序列。`main()` 函数中,我们创建了一个待排序的数组,并调用 `mergeSort()` 进行排序,最后打印排序后的数组。 ### 4. ...
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
Java实现归并排序 Java 实现归并排序是一种常用的排序算法,通过分治策略将原始数组分成小组,然后对每个小组进行排序,最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结: 基本思想 ...
### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...
MergeSort 函数是二路归并排序的主函数,它将待排序的记录分成多个部分,然后对每个部分进行排序,最后将已排序的部分合并成一个有序的序列。 实验结果 实验结果显示了二路归并排序的过程,每一趟的排序结果都会被...
在Java中实现归并排序,我们可以创建一个名为`MergeSort`的类来封装整个过程。归并排序的基本思想是将待排序的序列分成两个或更多的子序列,对每个子序列分别进行排序,然后将排序后的子序列合并成一个有序序列。这...
归并排序(Merge Sort)是一种高效的排序算法,其主要基于分治法(Divide and Conquer)的思想。在C++中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:分治法是计算机科学中常用的一种算法设计...
根据给定的信息,本文将对归并排序这一重要的数据结构算法进行深入剖析,重点讲解其核心思想、工作原理以及实际应用中的实现细节。 ### 归并排序简介 归并排序是一种采用分治策略的高效排序算法。其基本思想是:将...
归并排序是一种高效的排序算法,基于分治策略。在计算机科学中,分治法是一种将大问题分解为小问题来解决的方法。归并排序的基本思想是将待排序的数据分成两个或更多的子序列,分别对这些子序列进行排序,然后将排好...
归并排序的实现过程可以分为两个函数:Mergesort 函数和 Mergepass 函数。Mergesort 函数用于控制归并的流程,而 Mergepass 函数用于实现两两归并的操作。 4. 归并排序的时间复杂度分析 归并排序的时间复杂度为 O...