`
haoran_10
  • 浏览: 446255 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

排序算法(4)--归并排序

阅读更多
简介:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

 

一、主要步骤

将待排序数组[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

综上可知:

归并排序其实要做两件事:

(1)“分解”——将序列每次折半划分

(2)“合并”——将划分后的序列段两两合并后排序

 

二、演示过程
1、先看合并
(1)、两端相邻的有序子数组,arr[start]~arr[mid] 称为数组A和arr[mid+1]~arr[end] 称为数组B
(2)、每次各从数组A和数组B中取出一个值相比较,小的一个放到临时数组C
(3)、最后数组A和数组B中的数据取完时,数组C就是一个有序的合并后的数组。
(4)、最后在临时数组复制到原数组中
2、在看分解
(1)、先把数组分成最细,gap=1,然后把相邻的两个数据合并排序
(2)、然后设置gap=2,继续把相邻的两个数组合并。若子表个数为奇数,则最后一个子表无须和其他子表归并(即本趟处理轮空);
            若子表个数为偶数,则要注意到最后一对子表中后一个子表区间的上限为n-1。
(3)、直到gap等于数组的长度,数组合并完成
 
如图所示:


 
 
 
三、代码实现
@Override
public void sort(int[] arr) {
	mergeSort(arr);
}

private void merge(int[] array,int start,int mid,int end){
	int temp[] = new int[end-start+1];//临时数组
	
	int firstArrIndex = start;//第一段数组序列的下标
	int secondArrIndex = mid+1;//第二段数组序列的下标
	int tempArrIndex = 0;//临时存放数组的下标
	
	//1.扫描第一个数组序列和第二个数组序列
	while(firstArrIndex <=mid && secondArrIndex<=end){
		//1.1 当第一段数组小于第二段数组 未排序的首个元素时
		if(array[firstArrIndex] <=array[secondArrIndex]){
			temp[tempArrIndex] = array[firstArrIndex];
			firstArrIndex++;
		}else{//1.2 当第二段数组小于第一段数组 未排序的首个元素时
			temp[tempArrIndex] = array[secondArrIndex];
			secondArrIndex++;
		}
		
		tempArrIndex++;
	}
	
	//2.当第一段没有复制完全时,将剩余的数组全部复制到临时数组
	while(firstArrIndex<=mid){
		temp[tempArrIndex] = array[firstArrIndex];
		firstArrIndex++;
		tempArrIndex++;
	}
	
	
	//3.当第二段没有复制完全时,讲剩余的数组全部复制到临时数组
	while(secondArrIndex<=end){
		temp[tempArrIndex] = array[secondArrIndex];
		secondArrIndex++;
		tempArrIndex++;
	}
	
	//4.将临时数组复制到原始数组
	for(tempArrIndex=0,firstArrIndex=start;firstArrIndex<=end;tempArrIndex++,firstArrIndex++){
		array[firstArrIndex] = temp[tempArrIndex];
	}
}

private void mergeSort(int[] arr){
	for (int gap = 1; gap < arr.length; gap = 2 * gap) {
		int i=0;
		//归并gap长度的两个相邻子数组
		for(i=0; i+2*gap-1< arr.length; i = i + 2*gap) {
			merge(arr, i, i+gap-1, i+2*gap-1);
		}
		
		// 余下不足两个合并的子数组。保证第一个数组gap存在。
		if(i + gap - 1 < arr.length){
			merge(arr, i, i + gap - 1, arr.length - 1);
		}
	}
}
 

 

  • 大小: 197.3 KB
5
4
分享到:
评论
2 楼 haoran_10 2015-12-29  
yybing110 写道
这种算法 适用于什么情况呢?

归并过程中是不会改变元素的相对位置的,缺点是,它需要O(n)的额外空间。但是很适合于多链表排序。
1 楼 yybing110 2015-12-29  
这种算法 适用于什么情况呢?

相关推荐

    归并排序 - 排序算法 - 归并算法

    归并排序是一种分而治之的排序算法,其思想是将待排序数组分割成若干个子序列,对每个子序列进行排序,然后将排序好的子序列合并成一个有序的序列。该算法的实现包括两个主要的步骤:分割和合并。首先,递归地将数组...

    VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序

    本篇文章主要探讨了如何在VC++环境中利用多线程技术来实现三种经典的排序算法:冒泡排序、快速排序和归并排序,并对它们的性能进行了比较。 首先,冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次...

    最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构

    本文将对快速排序、归并排序、堆排序等常见排序算法进行比较和分析,探讨它们的优缺点和适用场景。 首先, let's 看一下这些排序算法的时间复杂度和空间复杂度: | 排序算法 | 平均情况 | 最好情况 | 最坏情况 | ...

    排序算法汇总--各类排序算法

    排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排

    算法设计-归并排序

    算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间

    最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构

    4.快速排序算法 快速排序算法是一种高效的排序算法,它的工作原理是通过选择一个元素作为pivot,然后将数组分为两个部分,以达到排序的目的。快速排序算法的时间复杂度为O(n log n),因此它适合大规模的数据排序。 ...

    详解Java常用排序算法-归并排序

    Java常用排序算法-归并排序 归并排序是一种分治思想的排序算法,其基本思想是将待排序的数组分成若干个子序列,每个子序列都是有序的,然后再将子序列合并成一个有序的数组。这种算法的时间复杂度为O(n log n),...

    各类排序算法整理--C语言描述--本人编写

    各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序

    归并排序,排序等算法,数据结构,快速排序,链表排序

    本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...

    经典算法的C#源码实现

    经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - 鸡尾酒排序Cocktail sort 经典排序算法 - 希尔排序Shell sort 经典排序算法 - ...

    快速排序算法以及归并算法

    根据给定的文件信息,我们将深入探讨两种经典的排序算法——快速排序和归并排序,并结合Java语言实现进行详细解析。 ### 快速排序算法 快速排序是一种高效的排序算法,采用分而治之的策略,其核心思想是选择一个...

    排序算法--免费

    本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序以及归并排序,并结合C++编程语言进行讲解。 1. **选择排序(Selection Sort)** - 选择排序是一...

    数据结构排序算法汇总包-直接插入排序 折半插入排序 2—路插入排序 表插入排序 希尔排序 起泡排序 快速排序 简单选择排序 树形选择排序 堆排序 归并排序链式基数排序

    实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...

    算法-数据结构和算法-14-归并排序.rar

    归并排序是一种高效的排序算法,基于分治策略。在计算机科学中,数据结构和算法是核心部分,因为它们直接影响程序的效率和性能。归并排序是排序算法中的一个重要概念,尤其在处理大量数据时,其稳定性及平均时间...

    算法设计实验报告-快速排序和归并排序

    本实验旨在通过对两种经典排序算法——快速排序和归并排序的研究与实现,深入理解它们的基本原理、时间复杂度,并通过编程实践比较这两种算法在不同数据规模下的性能表现。 #### 二、快速排序 **1. 基本思想** ...

    C++实现希尔、快速、堆排序、归并排序算法

    4. 归并排序的合并过程中要注意避免不必要的元素复制,可以使用指针或迭代器来减少内存操作。 这些排序算法各有优缺点,适用场景也不同。希尔排序适合处理大规模且接近有序的数据;快速排序在大部分情况下性能优秀...

    归并排序算法实现(排序算法系列1)

    归并排序是一种高效的、稳定的排序算法,由著名计算机科学家John W. Backus在1946年提出。它是基于分治策略的一种经典算法,适用于处理大量数据。在本系列的第一部分,我们将深入探讨归并排序的基本原理、实现过程...

    归并排序算法实现

    归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。归并排序在实际应用中非常广泛,尤其在处理大...

    排序算法图解--Document.zip

    在计算机科学领域,排序算法是数据结构中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如升序或降序)排列。本资料“排序算法图解”将深入探讨这一主题,通过可视化的方式帮助我们...

    数据结构--九种排序算法 --排序001.cpp

    此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!

Global site tag (gtag.js) - Google Analytics