`

归并排序

 
阅读更多

 

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

 

        首先考虑下如何将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

       代码如下:

 

	/**
	 * 将两个有序数列合并成一个有序数列
	 * @param a
	 * @param b
	 * @return
	 */
	public static int[] mergeArray(int[] a,int[] b){ 
		int i=0;
		int j=0;
		int k=0;
		int[] temp = new int[a.length+b.length];
		
		while(i<a.length&&j<b.length){
			if(a[i]<b[j])
				temp[k++] = a[i++];
			else
				temp[k++] = b[j++];			
		}
		
		while(i<a.length)
			temp[k++] = a[i++];
		
		while(j<b.length)
			temp[k++] = a[j++];
		
		return temp;
	}

 

        上述代码说明如下:

        假设我们有两个已经排序好的子序列。

               序列A:1 23 34 65

               序列B:2 13 14 87

       那么可以按照下面的步骤将它们归并到一个序列中。

             (1)首先设定一个新的数列C[8]。

             (2)A[0]和B[0]比较,A[0] = 1,B[0] = 2,A[0] < B[0],那么C[0] = 1

             (3)A[1]和B[0]比较,A[1] = 23,B[0] = 2,A[1] > B[0],那么C[1] = 2

             (4)A[1]和B[1]比较,A[1] = 23,B[1] = 13,A[1] > B[1],那么C[2] = 13

             (5)A[1]和B[2]比较,A[1] = 23,B[2] = 14,A[1] > B[2],那么C[3] = 14

             (6)A[1]和B[3]比较,A[1] = 23,B[3] = 87,A[1] < B[3],那么C[4] = 23

             (7)A[2]和B[3]比较,A[2] = 34,B[3] = 87,A[2] < B[3],那么C[5] = 34

             (8)A[3]和B[3]比较,A[3] = 65,B[3] = 87,A[3] < B[3],那么C[6] = 65

             (9)最后将B[3]复制到C中,那么C[7] = 87。归并完成。

        可以看出合并有序数列的效率是比较高的,可以达到O(n).

 

        解决了上面合并有序数列问题,再来看归并排序就比较简单了。

        其基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?

        可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。

        这样通过先递归的分解数列,再合并数列就完成了归并排序。

        算法如下图所示:

 
   

     

     代码实现如下:

 

public class MergeSort {
	
	public static void main(String[] args) {
		int[] a = {10,4,6,3,8,2,5,7}; 
		mergeSort(a,0,7);
		
		System.out.println("------------------");
		print(a);
	}
	
	public static void mergeSort(int[] a,int first,int last){
		
		if(first<last){
			int mid = (first+last)/2;
			mergeSort(a,first,mid);
			mergeSort(a,mid+1,last);
			merge(a,first,mid,last);
			System.out.print("本次递归:"+first+" "+mid+" "+last+":  ");
			print(a);
			System.out.println();
		}
		
	}
	
	private static void merge(int[] a,int first,int mid,int last) {
		int i = first;
		int j = mid+1;
		int k = 0;
		int[] temp = new int[a.length];
		while(i<=mid&&j<=last){
			if(a[i]<a[j])
				temp[k++] = a[i++];
			else
				temp[k++] = a[j++];
		}
		
		while(i<=mid)
			temp[k++] = a[i++];
		
		while(j<=last)
			temp[k++] = a[j++];
		
		//再把临时空间的元素拷到a上
		for(int t=0;t<k;t++)
			a[first+t] = temp[t];//注:不是a[t] = temp[t],因为数组是按引用传递,不是按值传递
	}

}
 其输出结果如下:

 

本次递归:0 0 1:  4 10 6 3 8 2 5 7 
本次递归:2 2 3:  4 10 3 6 8 2 5 7 
本次递归:0 1 3:  3 4 6 10 8 2 5 7 
本次递归:4 4 5:  3 4 6 10 2 8 5 7 
本次递归:6 6 7:  3 4 6 10 2 8 5 7 
本次递归:4 5 7:  3 4 6 10 2 5 7 8 
本次递归:0 3 7:  2 3 4 5 6 7 8 10 
------------------
2 3 4 5 6 7 8 10 

     其代码实现和结果分析如下:


        复杂度分析:

        归并排序是稳定的,它的最差,平均,最好时间都是O(nlogn)。但是它需要额外的存储空间,这在某些内存紧张的机器上会受到限制。

        归并算法是又分割和归并两部分组成的。对于分割部分,如果我们使用二分查找的话,时间是O(logn),在最后归并的时候,时间是O(n),所以总的时间是O(nlogn)。 

  • 大小: 269.2 KB
  • 大小: 10.3 KB
分享到:
评论

相关推荐

    MATLAB实现插入排序、二分归并排序、归并排序.rar

    在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...

    三路归并_C语言_三路归并排序_三路归并_

    **三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...

    归并排序C语言实现

    归并排序是一种高效的排序算法,基于分治策略。在C语言中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:归并排序的核心思想是将大问题分解为小问题来解决。首先将数组分为两半,分别对两半进行...

    归并排序算法实现

    ### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...

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

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

    java实现归并排序

    Java实现归并排序 Java 实现归并排序是一种常用的排序算法,通过分治策略将原始数组分成小组,然后对每个小组进行排序,最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结: 基本思想 ...

    直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码

    直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...

    归并排序 归并排序示例

    ### 归并排序详解 #### 一、归并排序简介 归并排序是一种采用分治策略的高效排序算法。其核心思想是将待排序数组分为若干子数组,这些子数组是已排序的,在合并这些子数组的过程中得到完全排序的数组。这种排序...

    二路归并排序

    二路归并排序 二路归并排序是指将两个有序表归并成一个有序表的过程。它是一种常用的排序算法,特别是在外部排序和数据库管理系统中。下面是对给定文件的知识点解释: 归并排序 归并排序是一种基于比较的排序算法...

    C语言二路归并排序算法

    ### C语言二路归并排序算法 #### 概述 归并排序是一种高效的排序算法,其基本思想是采用分治法(Divide and Conquer),将一个数组分成两个子数组,然后递归地对这两个子数组进行排序,最后将两个有序的子数组合并...

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

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

    归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    归并排序(Merge Sort)是一种基于分治策略的高效排序算法,由计算机科学家John W. Backus于1945年提出。它的工作原理可以分为三个主要步骤:分解、解决和合并。 1. 分解:将原始数据序列分成两个相等(或接近相等...

    数据结构堆排序 快速排序 归并排序

    本文将深入探讨三种常见的高效排序算法:堆排序、快速排序和归并排序。它们都是基于不同的原理和策略,具有各自的优势和适用场景。 首先,堆排序是一种基于比较的排序算法,利用了二叉堆的数据结构。二叉堆是一个...

    用单链表和队列实现归并排序

    归并排序是一种高效的排序算法,基于分治策略。在计算机科学中,分治法是一种将大问题分解为小问题来解决的方法。归并排序的基本思想是将待排序的数据分成两个或更多的子序列,分别对这些子序列进行排序,然后将排好...

    插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序

    以下是关于"插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序"这十大经典排序算法的详细解释: 1. 插入排序:插入排序是一种简单的排序算法,它通过构建有序...

    归并排序Java_归并排序_

    归并排序是一种高效的排序算法,基于分治策略。在Java中实现归并排序,我们可以创建一个名为`MergeSort`的类来封装整个过程。归并排序的基本思想是将待排序的序列分成两个或更多的子序列,对每个子序列分别进行排序...

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

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

    归并排序、基数排序算法比较

    试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...

    归并排序插入排序C++代码

    归并排序和插入排序是两种常见的排序算法,它们在计算机科学和编程领域有着广泛的应用。归并排序是一种基于分治思想的排序算法,而插入排序则是一种简单直观的排序算法,适用于小规模或部分有序的数据。 **归并排序...

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

    本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...

Global site tag (gtag.js) - Google Analytics