java實現(xiàn)歸并排序

silvertheo 發(fā)布于2019-08-16 12:32 / 1441人閱讀

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

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

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

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

代碼實現(xiàn)如下：

    public static void mergeSort(int[] nums) {
        //創(chuàng)建與原數(shù)組相同長度的數(shù)組
        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) {
            //從中間將數(shù)組分成兩半
            int mid = (left + right) >> 1;
            mergeSort(nums, temp, left, mid);
            mergeSort(nums, temp, mid+1, right);
            //將兩個數(shù)組重新合并
            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;
        //對比左右兩個數(shù)組并將較小的數(shù)先放到輔助數(shù)組
        while(leftPos <= leftEnd && rightPos <= rightEnd) {
            if(nums[leftPos] <= nums[rightPos]) {
                temp[tmpPos++] = nums[leftPos++];
            }else {
                temp[tmpPos++] = nums[rightPos++];
            }
        }
        //把左邊數(shù)組剩下的原數(shù)放到輔助數(shù)組
        while(leftPos <= leftEnd) {
            temp[tmpPos++] = nums[leftPos++];
        }
        //把右邊數(shù)組剩下的原數(shù)放到輔助數(shù)組
        while(rightPos <= rightEnd) {
            temp[tmpPos++] = nums[rightPos++];
        }
        //把輔助數(shù)組復制到原數(shù)組
        for(int i = 0; i < numElements; i++,rightEnd--) {
            nums[rightEnd] = temp[rightEnd];
        }
    }

GPU云服務器云服務器 java歸并排序歸并排序二路歸并排序歸并排序算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71259.html

Java排序之歸并排序

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

gityuan 2019-08-15 18:10 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

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

zhou_you 2019-08-16 10:34 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

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

caoym 2019-07-31 10:56 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

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

microcosm1994 2019-08-20 16:30 評論0 收藏0
幾種常見排序算法

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

ChristmasBoy 2019-08-14 15:37 評論0 收藏0