歸并有遞歸和非遞歸兩種。
歸并的思想是：
1.將原數組首先進行兩個元素為一組的排序，然后合并為四個一組，八個一組，直至合并整個數組；
2.合并兩個子數組的時候，需要借助一個臨時數組，用來存放當前的歸并后的兩個數組；
3.將臨時數組復制回原數組對應的位置。
非遞歸的代碼如下：
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
package mergesort;import java.util.Arrays;import java.util.Random;import java.util.Scanner;//歸并排序的非遞歸算法public class MergeSort{ public static void main(String args[]){ MergeSort mer = new MergeSort(); int[] array = mer.getArray(); System.out.println("OriginalArray:" + Arrays.toString(array)); mer.mergeSort(array); System.out.println("SortedArray:" + Arrays.toString(array)); } public int[] getArray(){ Scanner cin = new Scanner(System.in); System.out.print("Input the length of Array:"); int length = cin.nextInt(); int[] arr = new int[length]; Random r = new Random(); for(int i = 0; i < length; i++){ arr[i] = r.nextInt(100); } cin.close(); return arr; } public void mergeSort(int[] a){ int len = 1; while(len < a.length){ for(int i = 0; i < a.length; i += 2*len){ merge(a, i, len); } len *= 2; } } public void merge(int[] a, int i, int len){ int start = i; int len_i = i + len;//歸并的前半部分數組 int j = i + len; int len_j = j +len;//歸并的后半部分數組 int[] temp = new int[2*len]; int count = 0; while(i < len_i && j < len_j && j < a.length){ if(a[i] <= a[j]){ temp[count++] = a[i++]; } else{ temp[count++] = a[j++]; } } while(i < len_i && i < a.length){//注意：這里i也有可能超過數組長度 temp[count++] = a[i++]; } while(j < len_j && j < a.length){ temp[count++] = a[j++]; } count = 0; while(start < j && start < a.length){ a[start++] = temp[count++]; } }} |
遞歸算法的實現代碼如下：
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
package mergesort;public class MergeSort { public static void mergeSort(int[] data,int left,int right){ //left,right均為數字元素下標 if(left<right){ int half=(left+right)/2; mergeSort(data,left,half); mergeSort(data,half+1,right); merge(data,left,right); } } public static void merge(int []a,int l,int h){ int mid=(l+h)/2; int i=l; int j=mid+1; int count=0; int temp[]=new int[h-l+1]; while(i<=mid&&j<=h){ if(a[i]<a[j]){ temp[count++]=a[i++]; }else{ temp[count++]=a[j++]; } } while(i<=mid){ temp[count++]=a[i++]; } while(j<=h){ temp[count++]=a[j++]; } count=0; while(l<=h){ a[l++]=temp[count++]; } } public static void printArray(int arr[]){ for(int k=0;k<arr.length;k++){ System.out.print(arr[k]+"\t"); } } public static int[] getArray(){// int[] data={4,2,3,1}; int[] data={543,23,45,65,76,1,456,7,77,88,3,9}; return data; } public static void main(String args[]){ int[]a=getArray(); System.out.print("數組排序前："); printArray(a); System.out.print("\n"); mergeSort(a,0,a.length-1); System.out.print("歸并排序后："); printArray(a); }} |
歸并排序的時間復雜度為O(n*log2n),空間復雜度為O(n)
歸并排序是一種穩定的排序方法。
到此這篇關于Java排序算法三之歸并排序的遞歸與非遞歸的實現示例解析的文章就介紹到這了,更多相關Java排序算法之歸并排序的遞歸與非遞歸內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/y999666/article/details/50942604
