`
huntfor
  • 浏览: 201564 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

排序算法(2)之归并排序——java实现

 
阅读更多

本文要讲的归并排序是继快速排序之后的又一常用排序算法,相似的是归并排序也是一种分治算法,因此,与快排一样,对于规模较大的问题,非常适用。

 

与快排相比,归并排序是稳定的,最重要的是其优点在于,其最差时间复杂度也是O(NlogN)

归并排序是将两个(两个以上按两两处理)有序表合并成一个新的有序表。这里要强调下,待归并的两个数列必须是有序的。具体原因见算法。

 

算法思想:

1.首先将原数列,分解成左右两部分

2.分别对左右两部分,进行分解处理

3.再讲子部分合并成为一个有序数列

 

代码框架如下:

static void merge(int[] a,int begin ,int end){
	if(begin == end){//只有一个元素的时候,认为已经排好序,跳出递归
	    return;
	}
	if(begin<end){
		int mid = (begin + end)/2;
		//分解左半部分和右半部分
1.                merge(a,begin,mid);
2.		merge(a,mid+1,end);
                               
                //将分解处理之后的部分进行合并
3.		mergeAndSort(a,begin,mid,end);
	}
}

 如果对递归不是特别熟悉的话,可以结合这个例子,手动的画出递归栈

      ↓  begin                                           ↓ mid                                                                           ↓ end 

5 4 2 7 9 1

 

接下来的重点是merge:

比如说

a的左半部分是:1 3 8,赋值给left[]

a的右半部分是:2 4 5,赋值给right[]

为了方便对比,我们将left和right的最后加一个哨兵元素MAX,这样就不比对最后一个元素做特殊处理了。

static void mergeAndSort(int[] a,int begin,int mid,int end){
	int[] left = new int[mid - begin + 2]; //多留出一个哨兵位
	int[] right = new int[end - mid + 1];
	for(int i = begin ; i <= end; i++){
		if(i <= mid){
			left[i - begin] = a[i];
		}else{
			right[i - mid - 1] = a[i];
		}
	}
	left[mid - begin + 1] = Integer.MAX_VALUE;
	right[end - mid] = Integer.MAX_VALUE;
	int i = 0;
	int j = 0;
	int index = begin;
	while(index <= end){//按照顺序,将左右两部分归并
		a[index++] = left[i] < right[j] ? left[i++] : right[j++];		
	}
}

 

 

附录:

全部源代码为:

package sort;

import java.util.Arrays;

public class Merge {
	
	static void merge(int[] a,int begin ,int end){
		if(begin == end){
			return;
		}
		if(begin<end){
			int mid = (begin + end)/2;
			merge(a,begin,mid);
			merge(a,mid+1,end);
			mergeAndSort(a,begin,mid,end);
		}
	}
	
	static void mergeAndSort(int[] a,int begin,int mid,int end){
		int[] left = new int[mid - begin + 2]; 
		int[] right = new int[end - mid + 1];

		for(int i = begin ; i <= end; i++){
			if(i <= mid){
				left[i - begin] = a[i];
			}else{
				right[i - mid - 1] = a[i];
			}
		}
		left[mid - begin + 1] = Integer.MAX_VALUE;
		right[end - mid] = Integer.MAX_VALUE;
		int i = 0;
		int j = 0;
		int index = begin;
		while(index <= end){
			a[index++] = left[i] < right[j] ? left[i++] : right[j++];			
		}
	}
	
	public static void main(String[] args) {
		int[] a = {1,9,5,7,4,6,3,8,11,24};
		merge(a,0,a.length - 1);
		System.out.println(Arrays.toString(a));
		//打印结果为:[1, 3, 4, 5, 6, 7, 8, 9, 11, 24]

	}
	
}

 

分享到:
评论

相关推荐

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

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

    算法-归并排序(java)(csdn)————程序.pdf

    归并排序算法-java 实现 在计算机科学中,排序算法是指将一组无序的数据按照某种规则排列成有序的数据。归并排序(Merge Sort)是一种常用的排序算法,属于分治算法的范畴。下面将详细介绍归并排序算法的java实现。...

    排序算法——归并排序

    自动生成500个随机数,然后对这500个随机数进行归并排序

    java算法——归并排序

    归并排序 在排序前,先建好一个长度等于原数组长度的临时数组

    最快的排序算法 图解八大排序算法——我见过的最详细的讲解(转),排序算法数据结构

    常见的排序算法有八种,即选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、.radix 排序和基数排序。 一、分类 内部排序和外部排序是两种基本的排序分类。内部排序是指待排序记录存放在计算机随机...

    快速排序与归并排序的算法比较实验报告

    这篇实验报告将深入探讨两种经典的排序算法——快速排序和归并排序,通过对它们在Java环境中的实现和性能测试,揭示它们在处理不同规模数据时的效率差异。 **快速排序(Quick Sort)** 快速排序由C.A.R. Hoare在...

    算法可视化系列——排序算法——冒泡排序

    - **冒泡排序**:最简单的排序算法之一,时间复杂度为O(n^2)。 2. **冒泡排序步骤**: - 遍历数组,比较相邻元素的值。 - 如果前一个元素大于后一个元素,则交换它们的位置。 - 这个过程会持续n-1轮(对于n个...

    各种排序算法java实现

    标题 "各种排序算法java实现" 涉及到的是计算机科学中的一个重要领域——算法,特别是排序算法在Java编程语言中的具体应用。排序算法是数据结构与算法分析中的基础部分,它们用于将一组数据按照特定顺序排列。在这个...

    算法可视化系列——排序算法——选择排序

    **选择排序**是一种简单直观的排序算法,它的工作原理如下:...在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等通常会优先考虑。然而,对于教学和理解排序算法的基本原理,选择排序是一个很好的起点。

    《Java数据结构和算法》学习笔记(2)——4种简单排序算法

    这些算法虽然在复杂度上不如高级排序算法如快速排序或归并排序,但它们提供了基础的排序逻辑,有助于理解更复杂的算法思想。 首先,我们来详细讲解插入排序(Insertion Sort)。插入排序的工作原理类似于我们手动...

    排序算法-基于Java实现的排序算法之BubbleSort实现.zip

    总的来说,"排序算法_基于Java实现的排序算法之BubbleSort实现"这个项目提供了学习和实践冒泡排序算法的机会。通过分析和编写这样的代码,不仅可以加深对排序算法的理解,也能提升Java编程技巧。同时,它也提醒我们...

    数据结构与问题求解——java语言描述 源码

    例如,`Sort.java`可能包含了各种排序算法的实现,如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。每种排序算法都有其特定的时间复杂性和适用场景,通过阅读源码可以加深对它们的理解。 此外,...

    常用排序算法小结(附Java实现)

    文章可能涵盖了如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等多种经典的排序算法,并且通过Java代码进行了详尽的解释和实现。 1. 冒泡排序:这是一种简单的排序方法,通过重复遍历数组,比较相邻...

    排序算法-基于Java实现的排序算法之BogoSort实现.zip

    在学习排序算法时,除了关注效率高的算法如快速排序、归并排序等,了解这些效率低下的算法也能帮助我们更好地理解和对比各种排序算法的优劣。同时,BogoSort的Java实现也展示了如何在编程中运用随机数生成来实现随机...

    java版本排序算法

    ### Java版本排序算法详解 #### 插入排序 插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在Java中,我们可以创建一个`...

    数据结构与算法分析——Java语言描述

    常见的排序算法(如冒泡排序、快速排序、归并排序、堆排序)和查找算法(如线性查找、二分查找)都有详尽的解释和实例。此外,还包括动态规划、贪心算法、回溯法等高级算法思想。算法分析不仅关注实现,更强调时间...

    数据结构与算法答案——java语言描述

    本资料集是“数据结构与算法答案——java语言描述”,虽然全为英文内容,但其深入探讨了使用Java实现数据结构和算法的细节。 1. **数组**:数组是最基本的数据结构之一,它是一系列相同类型元素的集合,可以通过索...

    数据结构与算法分析——Java语言描述-带书签目录高清扫描版

    排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,各有优缺点,适用于不同的数据特性。查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。此外,高级算法如...

    排序算法(Java描述)

    本文将深入探讨两种经典的排序算法——选择排序和插入排序,并通过Java语言进行具体描述,旨在帮助读者理解这两种算法的工作原理、时间复杂度以及实际应用。 #### 选择排序:效率与简洁性的权衡 选择排序是一种简单...

Global site tag (gtag.js) - Google Analytics