国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

java實現歸并排序

silvertheo / 1439人閱讀

摘要：歸并排序是一種十分優秀的排序方法，在一開始學習的時候可能會對它的實現思路有點難以理解，不過當你想通了之后就會發現這種方法的絕妙之處。

歸并排序是一種十分優秀的排序方法，在一開始學習的時候可能會對它的實現思路有點難以理解，不過當你想通了之后就會發現這種方法的絕妙之處。


由上圖應該可以很清楚的理解到歸并排序的基本步驟就是
1.先把一個數組以二分法的方式遞歸的分組，（分）
2.然后再將相鄰的兩個數組進行作對比，把兩個已排序好的子數組中的數字由小到大（由大到小）地放到輔助數組temp[]中，（合）
3.最后再把輔助數組中的元素復制到原數組中返回。

這種排序的時間復雜度為O(NlgN),同時需要O(N)的輔助空間——保存N個元素。
這是一種穩定的算法。

代碼實現如下：

    public static void mergeSort(int[] nums) {
        //創建與原數組相同長度的數組
        int[] temp = new int[nums.length];
        mergeSort(nums, temp, 0, nums.length-1);
    }

    private static void mergeSort(int[] nums, int[] temp, int left, int right) {

        if(left < right) {
            //從中間將數組分成兩半
            int mid = (left + right) >> 1;
            mergeSort(nums, temp, left, mid);
            mergeSort(nums, temp, mid+1, right);
            //將兩個數組重新合并
            merge(nums, temp, left, mid+1, right);
        }
    }

    private static void merge(int[] nums, int[] temp, 
            int leftPos, int rightPos, int rightEnd) {
        
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        //對比左右兩個數組并將較小的數先放到輔助數組
        while(leftPos <= leftEnd && rightPos <= rightEnd) {
            if(nums[leftPos] <= nums[rightPos]) {
                temp[tmpPos++] = nums[leftPos++];
            }else {
                temp[tmpPos++] = nums[rightPos++];
            }
        }
        //把左邊數組剩下的原數放到輔助數組
        while(leftPos <= leftEnd) {
            temp[tmpPos++] = nums[leftPos++];
        }
        //把右邊數組剩下的原數放到輔助數組
        while(rightPos <= rightEnd) {
            temp[tmpPos++] = nums[rightPos++];
        }
        //把輔助數組復制到原數組
        for(int i = 0; i < numElements; i++,rightEnd--) {
            nums[rightEnd] = temp[rightEnd];
        }
    }

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71259.html

相關文章

  • Java排序之歸并排序

    摘要：排序之歸并排序簡介歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合并排序。 Java排序之歸并排序 1. 簡介 歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合...

    gityuan 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    caoym 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    microcosm1994 評論0 收藏0

  • 幾種常見排序算法

    摘要：本文介紹幾種常見排序算法選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序，對算法的思路性質特點具體步驟實現以及圖解進行了全面的說明。最后對幾種排序算法進行了比較和總結。 本文介紹幾種常見排序算法（選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序），對算法的思路、性質、特點、具體步驟、java實現以及trace圖解進行了全面的說明。最后對幾種排序算法進行了比較和總結。 寫...

    ChristmasBoy 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<