顾名思义,归并排序的核心思想就是“归并”,将两个有序的数列进行“二路归并”能够非常快速的实现合并成一个有序数列:
public static void mergeArray(int[] array,int[] temp,int low,int midLoc,int high){ int i=low; int j=midLoc+1; int k=0; while(i<=midLoc&&j<=high){ if(array[i]<array[j]){ temp[k++]=array[i]; i++; }else{ temp[k++]=array[j]; j++; } } while(i<=midLoc){ temp[k++]=array[i]; i++; } while(j<=high){ temp[k++]=array[j]; j++; } for(i=0;i<k;i++){ array[i+low]=temp[i]; } }
使用这种思想,可以递归的将一个无序的数列切割成一个个的小子数列,直到最小长度1,然后两两之间进行归并,最终就能够实现数列的整体有序了:
import java.util.Scanner; public class MergeSort{ public static void main(String args[]){ Scanner scanner=new Scanner(System.in); int total=scanner.nextInt(); int[] array=new int[1024]; for(int i=0;i<total;i++){ array[i]=scanner.nextInt(); } //这里定义一个临时数组以提高效率(只定义这一个) int temp[]=new int[1024]; mergeSort(array,0,total-1,temp); output(array,total); } public static void output(int[] array,int total){ for(int i=0;i<total;i++){ System.out.print(array[i] +" "); } System.out.println(); } public static void mergeSort(int[] array,int low,int high,int[] temp){ if(low<high){ int midLoc=(low+high)/2; mergeSort(array,low,midLoc,temp); mergeSort(array,midLoc+1,high,temp); mergeArray(array,temp,low,midLoc,high); } } public static void mergeArray(int[] array,int[] temp,int low,int midLoc,int high){ int i=low; int j=midLoc+1; int k=0; while(i<=midLoc&&j<=high){ if(array[i]<array[j]){ temp[k++]=array[i]; i++; }else{ temp[k++]=array[j]; j++; } } while(i<=midLoc){ temp[k++]=array[i]; i++; } while(j<=high){ temp[k++]=array[j]; j++; } for(i=0;i<k;i++){ array[i+low]=temp[i]; } } }
输入N个数作为数组的长度,然后输入N个无序的整数,回车即可查看排序的结果:
写道
输入:
10
1 4 7 2 5 8 3 6 9 0
输出:
0 1 2 3 4 5 6 7 8 9
10
1 4 7 2 5 8 3 6 9 0
输出:
0 1 2 3 4 5 6 7 8 9
相关推荐
《数据结构》严蔚敏版——归并排序
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
关于序列的归并排序,涉及到序列的长度
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
随机产生1000个0~9的数,并分别用堆排序,快速排序,归并排序将产生的这1000个随机数排序,并将排序结果写入文件
数据结构中的内部排序法 归并排序 非常的好用
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
数据结构-归并排序 PPT文档
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
2.归并排序;3.基数排序。 北工大电控学院《数据结构与算法》课程的其它章节实验及作业程序代码亦已在本站上传,需要的同学可进入作者的空间或通过搜索获取。本代码为上传者原创,仅供个人学习参考使用,请勿自行在...
归并排序 实验题目:归并排序 实验要求:对输入的一组数据利用归并排序算法进行排序并输出 1 需求分析 本实验要求对输入的一组数据利用归并排序算法进行排序并输出。 归并排序是利用归并过程的算法。所谓归并,是指...
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
归并排序 经典数据结构算法 ppt.
数据结构 排序算法 快速排序 堆排序 冒泡 选择排序 折半排序 希尔排序 归并排序 插入
算法-数据结构之归并排序.rar
(1)输入一组数,用递归和非递归程序实现归并排序 (2)分析归并排序的复杂度 (3)将归并排序的思想用于外部排序中
数据结构上机:题目: 排序 输人10个整数,分别用希尔排序、快速排序、直接选择排序和归并排序实现由小到大排序并输出排序结果。
数据结构课件:第10章 排序2选择排序归并排序基数排序.pptx
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
本章主要介绍一些常用的排序算法:插入排序、交换排序、选择排序、归并排序和基数排序。这里介绍的排序算法都是基于待排序的数据元素序列构成的线性表采用顺序存储结构,即采用数组存储,并且默认为按关键字非递减...