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

常见内部排序算法之归并排序

阅读更多
常见内部排序算法之归并排序
来自百度百科的解释:
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的(一开始每个子序列只有一个,也是有序)。然后再把有序子序列合并为整体有序序列。
算法描述:
归并操作的过程如下:
    申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    设定两个指针,最初位置分别为两个已经排序序列的起始位置
    比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    重复步骤3直到某一指针达到序列尾
    将另一序列剩下的所有元素直接复制到合并序列尾
还是图解比较有说服力:网上找的图

下面是源代码:纯属个人理解,如有错误,欢迎指正!
package test.aglorith;

import java.util.Arrays;

public class MergeSort{
	public static void sort(int[] data){
		int data_len=data.length;
		int group=1;
		while(group<=data_len){
			for(int i=0;i<data_len-1;i=i+group*2){
				merge(data,i,group);
			}
			System.out.println(Arrays.toString(data)+"--每几个为一组--"+group);
			group=2*group;
		}
	}
	public static void merge(int[] data,int i,int group){
		int j=i+group;//设置右边是移动指针
		int count1=group;//左边数组元素个数
		int count2=group;
		//出现单个分组,即不用管
		if(data.length-j<0){
			return;
		}
		//可能会出现右边数组相对比较少,例如:最后两组,一组四个,一组三个
		if(data.length-j<group){
			count2=data.length-j;
		}
		//定义一个备用数组
		int temp_size=count1+count2;
		int[] temp=new int[temp_size];
		int k=0;//备用数组还剩多少空闲
		//迁移到备用数组
		while(i<j&&count1>0&&count2>0){
			if(data[i]<=data[j]){temp[k]=data[i];i++;count1--;}
			else{temp[k]=data[j];j++;count2--;}
			k++;
		}
		if(count1==0){while(k<temp_size){temp[k]=data[j];k++;j++;}}
		if(count2==0){while(k<temp_size){temp[k]=data[i];k++;i++;}}
		//把备用数组的有序数组迁回原数组
		int n=temp_size;
		while (n>0) {
			j--;n--;
			data[j]=temp[n];
		}
	}
	public static void main(String[] args){
		int[] data=new int[]{10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前");
		System.out.println(Arrays.toString(data));
		System.out.println("------------");
		sort(data);
	}
}


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

相关推荐

    数据结构课程设计(内部排序算法比较_C语言)

    常见的内部排序算法包括但不限于: 1. **直接插入排序**:逐个遍历列表中的每个元素,将其插入到已排序序列的正确位置。适用于小规模数据集。 2. **冒泡排序**:重复遍历待排序序列,每次遍历时比较相邻两个元素,...

    内部排序算法分析

    本主题将深入探讨内部排序算法,并结合C语言代码进行解析。内部排序,顾名思义,是指数据在主存储器(内存)内完成的排序过程,与外部排序相对,后者通常用于处理超出内存容量的大数据集。 1. **基本排序算法**: ...

    数据机构综合课设内部排序算法比较.docx

    本篇文章将深入探讨10种常见的内部排序算法,包括它们的基本思想、比较次数和移动次数的计算,以便更直观地理解不同算法的效率。 1. **直接插入排序**: 直接插入排序是一种简单的排序算法,它通过比较新元素与已...

    数据结构内部排序算法比较.doc

    常见的内部排序算法包括起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序等。这些算法各有优缺点,在不同场景下具有不同的适用性。因此,深入研究和比较这些排序算法对于提高数据处理效率具有重要...

    C语言数据结构内部排序算法及比较

    本文将深入探讨“C语言数据结构内部排序算法及比较”这一主题,结合个人课程作业的经验,对一些核心概念进行阐述,并对常见的内部排序算法进行比较。 首先,数据结构是组织和管理数据的方式,它包括数组、链表、树...

    常用的排序算法总结(各种内部排序算法和外部排序算法)

    本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先,排序的基本定义是:给定一个包含n个记录的序列,其关键字序列分别为K1, K2, ..., Kn,如果存在一个排列p1, p2, p3, ..., pn,使得关键字满足非...

    内部排序算法的性能分析

    本项目针对内部排序算法进行了性能分析,通过设计一个测试程序,对比了几种常见内部排序算法的关键字比较次数和移动次数,以帮助我们更直观地理解不同算法的效率差异。以下是关于内部排序算法的一些关键知识点: 1....

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

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

    内部排序算法分析与代码算法

    在本篇文章中,我们将深入探讨几种常见的内部排序算法,包括它们的原理、时间复杂度和空间复杂度,并通过代码实现来展示这些算法的运作过程。 1. 直接插入排序: 直接插入排序是一种简单的排序算法,它将数据分为已...

    内部排序算法性能分析

    本资源包含快速排序、希尔排序、冒泡排序、插入排序等六种常见的内部排序算法的性能分析,通过源代码和相关文档,我们可以深入理解这些算法的工作原理以及它们在不同情况下的性能表现。 1. **快速排序**:由C.A.R. ...

    数据结构课程设计(内部排序算法比较).

    内部排序算法是计算机科学基础课程——数据结构与算法中的核心内容之一。通过学习不同的内部排序算法,可以深刻理解算法的设计思想及其实现方法,同时也能为解决实际问题提供多种选择方案。 ### 常见的内部排序算法...

    【排序结构5】 基于比较的内部排序总结

    以上是常见的基于比较的内部排序算法,每种都有其适用场景和优缺点。在实际应用中,选择合适的排序算法要考虑数据规模、数据特性以及时间与空间复杂度的需求。例如,对于大数据量且部分有序的数组,快速排序通常优于...

    数据结构课程设计(内部排序算法比较)

    描述中提到,该设计已经通过了C语言的验证并能顺利运行,这意味着学生可能实现了如快速排序、归并排序、堆排序、插入排序、选择排序、冒泡排序、希尔排序等常见内部排序算法。每种算法都有其独特性,适用于不同的...

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

    归并排序是一种稳定的排序算法,同样基于分治法。它将数组分成两半,递归地排序每一半,然后将两个已排序的半数组合并成一个有序数组。 #### Java 实现代码分析 `Project17_Merge` 类展示了归并排序的实现。其关键...

    各种内部排序算法的比较

    1. **冒泡排序**:是最简单的排序算法之一,通过重复遍历数组,比较相邻元素并交换位置来实现排序。时间复杂度为O(n^2),适用于小规模或部分有序的数据。 2. **选择排序**:每次从未排序部分找到最小(或最大)元素...

    C++排序算法之归并排序源码

    ### C++排序算法之归并排序源码解析 #### 归并排序简介 归并排序是一种高效的、基于分治策略的排序算法。它利用了分而治之的思想,通过递归地将数组分成越来越小的部分,然后将这些部分重新合并为更大的、已排序的...

    九大内部排序算法打包下载

    本资源包包含了九种经典的内部排序算法的源代码,涵盖了从基础到高效的多种方法,但遗憾的是未包含桶排序。以下是这些排序算法的详细介绍: 1. 冒泡排序(Bubble Sort): 冒泡排序是最简单的排序算法之一,通过...

    内部排序算法的比较

    本篇文章将深入探讨六种常见的内部排序算法:希尔排序、直接选择排序、快速排序、直接插入排序、堆排序以及冒泡排序。 希尔排序是一种基于插入排序的算法,由希尔在1959年提出。它通过将待排序数组按某个增量分组,...

    内部排序小结 包括几乎所有的内部排序算法

    本篇内容主要总结了多种内部排序算法,包括它们的特点、效率以及适用场景。 1. 选择排序(Selection Sort):不稳定排序,平均时间复杂度为O(n^2)。它通过反复遍历待排序的数据,每次找到最小(或最大)的元素,...

Global site tag (gtag.js) - Google Analytics