归并算法排序
算法思想
- 1.简单地将原始序列划分为两个子序列
- 2.分别对每个子序列递归排序
- 3.最后将排好序的子序列合并为一个有序的序列,即归并过程
归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
java 代码
/** * 内部排序算法之归并排序 * 默认按照从小到大进行排序操作 * @author 小浩 * @创建日期 2015-3-27 */ public class Test{ public static void main(String[] args) { //需要进行排序的数组 int[] array=new int[]{8,3,2,1,7,4,6,5}; //输出原数组的内容 printResult(array); //归并排序操作 sort(array,0,array.length-1); //输出排序后的相关结果 printResult(array); } /** * 归并排序 * @param array */ private static void sort(int[] array,int i,int j) { if(i<j) { int middle=(i+j)/2; //递归处理相关的合并事项 sort(array,i,middle); sort(array,middle+1,j); merge(array,i,middle,j); } } /** * 合并相关的数组内容 * 同时使合并后的数组仍然有序 * @param array * @param i * @param middle * @param j * 4 5 6 9 10 11 * */ private static void merge(int[] array, int i, int middle, int j) { //创建一个临时数组用来存储合并后的数据 int[] temp=new int[array.length]; int m=i; int n=middle+1; int k=i; while(m<=middle&&n<=j) { if(array[m]<array[n]) temp[k++]=array[m++]; else temp[k++]=array[n++]; } //处理剩余未合并的部分 while(m<=middle) { temp[k++]=array[m++]; } while(n<=j) { temp[k++]=array[n++]; } //将临时数组中的内容存储到原数组中 while(i<=j) { array[i]=temp[i++]; } } /** * * 输出相应数组的结果 * @param array */ private static void printResult(int[] array) { for(int value:array) System.out.print(" "+value+" "); System.out.println(); } /** * 交换数组中两个变量的值 * @param array * @param i * @param j */ private static void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } }
排序算法的基本概念的讲解
时间复杂度:需要排序的的关键字的比较次数和相应的移动的次数。
空间复杂度:分析需要多少辅助的内存。
稳定性:如果记录两个关键字的A和B它们的值相等,经过排序后它们相对的位置没有发生交换,那么我们称这个排序算法是稳定的。
相关推荐
二路归并算法 排序 归并排序
自己编写的基于java的快速排序和归并算法
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
根据算法导论实现的归并排序算法
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
本人自己写的一些排序算法,这是系列1归并排序算法实现,
易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合并
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
归并排序算法,有程序和复杂性分析,还有解释,挺清楚的,很有用
归并算法思想总结
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
归并排序算法C语言版
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
算法练习,仅供参考 用递归实现的一个归并算法 void Merge(int *A,int p,int q,int r)实现对已排序的两部分合并 void Merge_sort(int *A,int p,int r) 调用上述函数实现排序
完整的实现了归并排序的算法,使用C语言实现,相信看过本程序之后,会对归并排序了如指掌
对于归并算法的四点改进 1.不回写,可以减少一半的数组移动 2.不递归 ,可以加快执行速度 3.无逆序,分段的时候递增的为一段,段数不确定 4.与插入相结合,因为数列个数在16以内的话插入排序会比归并排序要快
排序算法之瑰宝算法:包括2-路归并算法实现。
C++归并排序算法程序,很好,谨供大家参考