本文最先發布于本人個人博客
http://www.lovestblog.cn
下面簡單的說說歸并排序，所謂歸并排序就是說把輸入數組分成兩組當然也可以大于2組，一般我們是等量的分成2組，通過遞歸我們可以把長度為n的數組分成n個數組，我們通過一定的關鍵字比較把兩兩結合成一個有序的數組，然后回溯到原數組大小的有序數組，具體的我就不多說了，因為比較簡單，到網上可以找些相關文章看看什么是歸并排序，歸并排序算法可以再O(nlogn)的時間內對長度為n的序列完成排序，至于合并兩個有序數組，假如這兩個數組的長度分別為m和n，那么我們只需要O(n+m)的時間久可以完成對這兩個有序數組的合并，下面還是代碼說明之：
package org.rjb.Sort;
/** *//**
* 歸并排序（升序排列）
* @author ljp
*
*/
public class MergeSort 
{
/** *//**
* 對原始數組進行平等劃分為兩個子數組
* @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];
}
//遞歸對子數組進行劃分
sort(nums1);
sort(nums2);
//把子數組排序后的結果進行合并
merge(nums,nums1,nums2);
}
/** *//**
* 合并兩個有序的子數組為一個有序的數組
* @param nums 合并之后的數組
* @param num1 有序的子數組
* @param num2 有序的子數組
*/
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){//如果第一個數組已經全部比較完了，那么我們只要直接復制第二個數組的條目到合并數組中即可
e=num2[k2++];
}else if(k2>n2){//如果第二個數組已經全部比較完了，那么我們只要直接復制第一個數組的條目到合并數組中即可
e=num1[k1++];
}else if(num1[k1]>num2[k2]){//把比較的兩個條目中關鍵值小的放到合并數組中
e=num2[k2++];
}else{
e=num1[k1++];
}
nums[k++]=e;
}
}
/** *//**
* 主函數
* @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
你假笨 閱讀(1224)
評論(0) 編輯 收藏