本文最先發(fā)布于本人個(gè)人博客
http://www.lovestblog.cn
下面簡單的說說歸并排序，所謂歸并排序就是說把輸入數(shù)組分成兩組當(dāng)然也可以大于2組，一般我們是等量的分成2組，通過遞歸我們可以把長度為n的數(shù)組分成n個(gè)數(shù)組，我們通過一定的關(guān)鍵字比較把兩兩結(jié)合成一個(gè)有序的數(shù)組，然后回溯到原數(shù)組大小的有序數(shù)組，具體的我就不多說了，因?yàn)楸容^簡單，到網(wǎng)上可以找些相關(guān)文章看看什么是歸并排序，歸并排序算法可以再O(nlogn)的時(shí)間內(nèi)對長度為n的序列完成排序，至于合并兩個(gè)有序數(shù)組，假如這兩個(gè)數(shù)組的長度分別為m和n，那么我們只需要O(n+m)的時(shí)間久可以完成對這兩個(gè)有序數(shù)組的合并，下面還是代碼說明之：
package org.rjb.Sort;
/** *//**
* 歸并排序（升序排列）
* @author ljp
*
*/
public class MergeSort 
{
/** *//**
* 對原始數(shù)組進(jìn)行平等劃分為兩個(gè)子數(shù)組
* @param nums
*/
public static void sort(int[] nums){
int n=nums.length;
if(n<=1)
return;
int nums1[]=new int[n/2];
int nums2[]=new int[n-n/2];
for(int i=0,j=nums1.length;j<nums.length;i++,j++){
if(i<nums1.length){
nums1[i]=nums[i];
}
nums2[i]=nums[j];
}
//遞歸對子數(shù)組進(jìn)行劃分
sort(nums1);
sort(nums2);
//把子數(shù)組排序后的結(jié)果進(jìn)行合并
merge(nums,nums1,nums2);
}
/** *//**
* 合并兩個(gè)有序的子數(shù)組為一個(gè)有序的數(shù)組
* @param nums 合并之后的數(shù)組
* @param num1 有序的子數(shù)組
* @param num2 有序的子數(shù)組
*/
public static void merge(int[] nums,int num1[],int num2[]){
int n1=num1.length-1;
int n2=num2.length-1;
int k=0;
int k1=0,k2=0;
while(k1<=n1||k2<=n2){
int e=0;
if(k1>n1){//如果第一個(gè)數(shù)組已經(jīng)全部比較完了，那么我們只要直接復(fù)制第二個(gè)數(shù)組的條目到合并數(shù)組中即可
e=num2[k2++];
}else if(k2>n2){//如果第二個(gè)數(shù)組已經(jīng)全部比較完了，那么我們只要直接復(fù)制第一個(gè)數(shù)組的條目到合并數(shù)組中即可
e=num1[k1++];
}else if(num1[k1]>num2[k2]){//把比較的兩個(gè)條目中關(guān)鍵值小的放到合并數(shù)組中
e=num2[k2++];
}else{
e=num1[k1++];
}
nums[k++]=e;
}
}
/** *//**
* 主函數(shù)
* @param args
*/
public static void main(String args[]){
int[] nums={10,2,3,7,4,9,1};
sort(nums);
for(int i=0;i<nums.length;i++){
System.out.print(nums[i]+" ");
}System.out.println();
}
}
posted on 2009-05-29 16:55
你假笨 閱讀(1221)
評論(0) 編輯 收藏