歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

歸並排序的Java實現

  歸並排序的優點不說了。

  做歸並排序之前,我先試著將兩個有序數組進行排序,合並成一個有序數組。

  思路:定義好兩個有序數組,理解的時候我先思考了數組只有一個數組的排序,然後是兩個元素的數組的排序,思路就有了,先比較兩個數組的首元素,誰更小就放入結果數組裡面,然後指針下移,繼續比較,直到有一個數組為空,停止比較,因為是有序數組,那麼不為空的數組後面的元素都比之前存入結果數組的要大,且是有序的,因此,只需將後面的數組存入結果數組即可。

  接下來是代碼實現:


/*

    * 分治算法利用

    * 兩個有序數組的合並

    * 將有序數組i,數組j,合並成c

    */

    public Integer[] sort(Integer[] i, Integer[] j, Integer[] c){

        c = new Integer[i.length+j.length];

        int i1 = 0;  //i的數組指針

        int j1 = 0; //j的數組指針

        int c1 = 0; //c的數組指針

        while(i1 < i.length&&j1 < j.length){

            if(i[i1] > j[j1]){

                c[c1++] = j[j1];

                j[j1++] = null;

            }else{

                c[c1++] = i[i1];

                i[i1++] = null;

            }

        }

        /*

        * i之後還有元素

        */

        while(i1<i.length){ 

            c[c1++] = i[i1];

            i[i1++] = null;

        }

        /*

        * j之後還有元素

        */

        while(j1 < j.length){

            c[c1++] = j[j1];

            j[j1++] = null;

        }

        return c;

    }

  以上實現了將兩個有序數組的合並,而歸並排序,那麼將一條無序數組分組成任意多個有序數組即可,並不需要確認是否是有序數組,一個數組裡一個元素肯定是有序的,那麼我要做的只是,遞歸實現數組分解,然後將有兩個序數組合並。

  將一個數組分解,可以用分治的方法,定義頭,尾,和中間指針,然後下次的遞歸,只需變換中間指針即可。

  而排序最開始只需要比較頭部的一個元素和尾部的一個元素;

  依次向上遞歸。

  算了,貼代碼吧。


public int[] mergeSort(int[] num,int first,int last){

        int mid = (first+last)/2;

        if(first < last){

            mergeSort(num,first,mid);

            mergeSort(num,mid+1,last);

            merge(num,first,mid,last);

        }

        return num;

    }

   

    public void merge(int[] num,int first,int mid,int last){

        int _left = first; //左指針

        int _right = mid+1; //右指針

        int[] temp = new int[last - first + 1];

        int temp_p = 0;

        while(_left<=mid&&_right<=last){

            if(num[_left]<num[_right]){

                temp[temp_p++] = num[_left++];

            }else{

                temp[temp_p++] = num[_right++];

            }

        }

        while(_left<=mid){

            temp[temp_p++] = num[_left++];

        }

        while(_right<=last){

            temp[temp_p++] = num[_right++];

        }

        _left = 0;

        //因為沒有返回數組,所以排序好的數組應該放在num數組裡面,直接覆蓋即可,注意下標。

        for(int i : temp){

            num[(_left++)+first] = i;

        }

    }

first,last為數組頭尾指針。

Copyright © Linux教程網 All Rights Reserved