`

归并排序

阅读更多

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

 

排序基本思想是:

      将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素,将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素,重复步骤2,直到所有元素排序完毕  

 

速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列

归并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组

 

稳定           时间复杂度O(nlogn)   n大时较好


      
 

public class MergeSort {
	/**
	 * 静态方法功能:给一个给定的数组用归并排序法排序
	 * @param a:待排序数组
	 * @param begin:开始下标
	 * @param end:终止下标
	 */
	public static void mergeSort(int a[], int begin, int end)
	{
		if (begin < end)
		{
			int a1[] = new int[end - begin + 1];

			int begin0 = 0;

			int mid = (begin + end) / 2;

			mergeSort(a, begin, mid);

			mergeSort(a, mid + 1, end);

			int begin1 = begin;

			int begin2 = mid + 1;

			int end1 = mid;

			int end2 = end;

			for (int i = 0; i < a1.length; i++)
			{
				if (begin1 <= end1 && begin2 <= end2)
				{
					if (a[begin1] < a[begin2])
					{
						a1[begin0] = a[begin1];
						begin0++;
						begin1++;
					}
					else
					{
						a1[begin0] = a[begin2];
						begin0++;
						begin2++;
					}
				}
				else
					break;
			}

			if (begin1 <= end1)
			{
				for (; begin0 < a1.length; begin0++)
				{
					a1[begin0] = a[begin1];
					begin1++;
				}
			}
			else
			{
				for (; begin0 < a1.length; begin0++)
				{
					a1[begin0] = a[begin2];
					begin2++;
				}
			}

			// 将排好序的结果填回原数组
			for (int i = 0; i < a1.length; i++)
			{
				a[begin + i] = a1[i];
			}
		}
	}
	
	public static void main(String[] args) throws Exception {

		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49 };

		mergeSort(a, 0, a.length - 1);

		for (int key : a) {
			System.out.format(" %d", key);
		}
	}

}

 

  • 大小: 32.1 KB
分享到:
评论

相关推荐

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

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

    归并排序C语言实现

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

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

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

    归并排序算法实现

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

    归并排序算法实现(排序算法系列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