Java常见排序算法之归并排序

    在学习算法的过程中,我们难免会接触很多和排序相关的算法。总而言之,对于任何编程人员来说,基本的排序算法是必须要掌握的。

从今天开始,我们将要进行基本的排序算法的讲解。Are you ready?Let‘s go~~~

1、排序算法的基本概念的讲解

     时间复杂度:需要排序的的关键字的比较次数和相应的移动的次数。

     空间复杂度:分析需要多少辅助的内存。

     稳定性:如果记录两个关键字的A和B它们的值相等,经过排序后它们相对的位置没有发生交换,那么我们称这个排序算法是稳定的。

              否则我们称这个排序算法是不稳定的。

   

    排序算法的常见分类:

    1、内部排序(最常见的一种排序方式,不需要借助第三方辅助存储工具)

    2、外部排序(需要借助外部存储来辅助完成相关的排序操作)

        如果参与排序的数据元素非常的多,数据量非常的大,计算机无法把整个排序过程放到内存中进行的话,

        我们必须借助外部存储器如磁盘来完成,这种排序方式,我们称之为外部排序。

        其中外部排序最常见的就是多路归并排序,即将原始文件分解成多个能够一次性装入内存的部分,分别把每一部分调入

        内存完成相应的排序,接下来在对多个有序的外部文件进行多路归并排序。

  

   对于我们绝大多数的程序员而言,我们经常遇到的为内部排序。接下来我们将要对常见的内部排序进行相应的讲解。

    今天要讲解的内部排序为:

   归并排序

  1.归并排序的基本概念的讲解

 

归并排序建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个
有序表,称为二路归并。
 
归并过程为:比较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]。
 
归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
总的比较次数为:3+4+4=11,;
逆序数为14;

 

  2.归并排序的Java代码实现

   

package com.yonyou.test;


/**
 * 内部排序算法之归并排序
 * 默认按照从小到大进行排序操作
 * @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;
	}
}

 

  

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。