欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序的算法实现

程序员文章站 2024-03-16 12:20:58
...



                               归并排序的算法实现

归并排序的基本思想是:

         将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。

        算法:

          1.把待排序的n个记录看作长度为1的有序序列,将相邻的子序列两两归并为长度为2或1的有序序列

           2.把得到的n/2个长度为2的有序序列再归并为长度为2*2的有序序列

           3.按照2的方式,重复对相邻的有序子序列进行归并操作,直到成为一个有序序列为止。

排序以一下方式进行:
归并排序的算法实现
 一下是我的算法实现:


 

public void merge_sort(int[]data,int left,int right){
		
		if(left<right){
			int mid=(left+right)/2;
			//递归调用将数组分组,将数组分成n个记录
			merge_sort(data, left, mid);
			merge_sort(data, mid+1, right);
			
			//将被分开的数组进行排序,合并
			merge(data,left,mid,right);
		}
	}
	private void merge(int[] data, int left, int mid, int right) {
		int i=0,k=0;  
		//用于控制合并过程时下标的处理
		int begin1=left,end1=mid,begin2=mid+1,end2=right;
		//用于存放数据
		int []temp=new int[right-left+1];
		//开始比较赋值
		while(begin1<=end1&&begin2<=end2){
			//依次比较两个排好序的子序列,最初两个子序列中最小元素放入临时数组
			if(data[begin1]<data[begin2]){
				temp[k]=data[begin1];
				begin1++;
			}
			else{
				temp[k]=data[begin2];
				begin2++;
			}
			k++;
		}
		
		//如果一个子序列已经完全放入临时数组,将剩余部分的数组放入临时数组
		while(begin1<=end1){
			temp[k++]=data[begin1++];
		}
		while(begin2<=end2){	
			temp[k++]=data[begin2++];	
		}
		
	
		  //将排好序的临时数组拷贝到原始数组
		k=0;
		for(i=left;i<=right;i++){
			data[i]=temp[k++];
		}
		
		
		
		
	}