本文實例講述了Java排序算法總結之歸并排序。分享給大家供大家參考。具體分析如下：
歸并操作(merge)，也叫歸并算法，指的是將兩個已經排序的序列合并成一個序列的操作。和快速排序類似，讓我們一起來看，歸并在Java中的實現。
歸并排序（Merge）是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。 將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。
歸并排序算法穩定，數組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時間復雜度為O(nlog(n))，算法不是自適應的，不需要對數據的隨機讀取。
工作原理：
1、申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
2、設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4、重復步驟3直到某一指針達到序列尾
5、將另一序列剩下的所有元素直接復制到合并序列尾
代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
////////////////public void mergeSort(){ long[] workSpace = new long[nElems]; recMergeSort(workSpace,0,nElems-1);}private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){ if(lowerBound == upperBound){ return; } else{ int mid=(lowerBound+upperBound)/2; recMergeSort(workSpace, lowerBound, mid); recMergeSort(workSpace, mid+1, upperBound); merge(workSpace, lowerBound, mid+1, upperBound); }}private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){ int j = 0; int lowerBound = lowPtr; int mid = highPtr - 1; int n = upperBound-lowerBound+1; while(lowPtr<=mid&&highPtr<=upperBound){ if(theArray[lowPtr]<theArray[highPtr]){ workSpace[j++]=theArray[lowPtr++]; } else{ workSpace[j++]=theArray[highPtr++]; } } while(lowPtr<=mid){ workSpace[j++] = theArray[lowPtr++]; } while(highPtr<=upperBound){ workSpace[j++] = theArray[highPtr++]; } for(j=0;j<n;j++){ theArray[lowerBound+j]=workSpace[j]; }} |
歸并排序是比較穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方.
希望本文所述對大家的java程序設計有所幫助。
