快捷導(dǎo)航

java實(shí)現(xiàn)歸并排序算法

更新時(shí)間：2016年01月20日 10:50:47 投稿：hebedich

在學(xué)習(xí)算法的過程中，我們難免會(huì)接觸很多和排序相關(guān)的算法?？偠灾瑢?duì)于任何編程人員來說，基本的排序算法是必須要掌握的。那么現(xiàn)在我們將要進(jìn)行基本的歸并排序算法的講解

歸并排序就是將未排序的數(shù)組進(jìn)行對(duì)半劃分成兩個(gè)數(shù)組，劃分后的數(shù)組只有原來數(shù)組的一半數(shù)量的元素。然后在對(duì)劃分的兩個(gè)數(shù)組再繼續(xù)劃分，循環(huán)此操作，直到劃分的數(shù)組中只有一個(gè)元素時(shí)停止劃分，然后對(duì)于劃分完成的數(shù)組進(jìn)行歸并排序操作。將兩個(gè)已經(jīng)劃分完成的數(shù)組合并成一個(gè)有序的數(shù)組，直到最后合并成一個(gè)包含所有元素的數(shù)組，合并排序操作完成。下面以圖形來演示下歸并排序的過程。

假設(shè)有一個(gè)未排序數(shù)組：｛3，2，4，1｝，下面為數(shù)組的劃分過程，先將數(shù)組對(duì)半劃分為｛3，2｝和｛4，1｝兩個(gè)數(shù)組。然后在對(duì)這兩個(gè)數(shù)組進(jìn)行劃分最后得到｛3｝，｛2｝，｛4｝，｛1｝四個(gè)數(shù)組，劃分完成。

接下來對(duì)數(shù)組進(jìn)行歸并，先將｛3｝和｛2｝這兩個(gè)數(shù)組合并成一個(gè)有序的數(shù)組｛2，3｝，同理對(duì)4，1進(jìn)行相同的操作，得到｛1，4｝，然后在將合并好的這兩個(gè)有序數(shù)組進(jìn)行合并，最后合并成｛1，2，3，4｝，歸并完成。

歸并排序算法用java代碼實(shí)現(xiàn)如下：

public static void MergeSort(int[] array,int head,int tail){
      // 判斷數(shù)組的頭部索引是否小于尾部索引
      if(head < tail){
        int middle = (head+tail)/2;
        MergeSort(array,head,middle);
        MergeSort(array,middle+1,tail);
        Merge(array,head,middle,tail);
      }  
    }

    public static void Merge(int[] array, int head, int middle, int tail) {
      // TODO Auto-generated method stub
      int[] temp = new int[tail - head + 1];
      int a = head;
      int b = middle + 1;
      int i = 0;
      // 對(duì)于兩個(gè)數(shù)組中的數(shù)進(jìn)行比較，將較小的值存放在臨時(shí)數(shù)組中
      while(a <= middle && b <=tail){
        
        if(array[a] < array[b]){
          temp[i++] = array[a++];  
        }
        else{
          temp[i++] = array[b++];
        } 
      }
      
      // 將未參與比較的數(shù)組中的數(shù)添加到臨時(shí)數(shù)組中
      while(a <= middle){
        temp[i++] = array[a++];
      }
      
      while(b <= tail){
        temp[i++] = array[b++];
      }
      
      // 將排好序的數(shù)組放回到array數(shù)組中
      System.arraycopy(temp,0,array,head,tail - head + 1);
    }

您可能感興趣的文章: