使用遞歸或循環實現歸并排序

public class MergeSort {public static void mergesort(int[] arr){process(arr,0,arr.length-1);}// 遞歸版本 left, rigth都是下標位置public static void process(int[] arr, int left, int right){if(left == right){return;}int mid = left + ((right-left)>>1);process(arr,left,mid);process(arr,mid+1,right);merge(arr,left,mid,right);}// 非遞歸版本public static void processCircle(int[] arr){int mergeSize = 1; // 步長int N = arr.length;while(mergeSize<N){// 當前左組的第一個位置int left = 0;while(left < N) {int mid = left + mergeSize - 1;if (mid >= N) {break;}int right = Math.min(mid + mergeSize, N - 1);merge(arr, left, mid, right);left = right + 1;}// 防止整數溢出if(mergeSize > N/2){break;}mergeSize <<= 1;}}public static void merge(int[] arr, int left, int mid, int right){int p1 = left;int p2 = mid+1;int[] tmp = new int[right-left+1];int i = 0;while(p1<=mid && p2<=right){tmp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while(p1<=mid){tmp[i++] = arr[p1++];}while(p2<=right){tmp[i++] = arr[p2++];}for (i = 0; i < tmp.length; i++) {arr[left+i] = tmp[i];}}public static int[] generateRandomArray(int maxSize, int maxValue){int[] arr = new int[(int)((maxSize+1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int)((maxValue+1)*Math.random())-(int)(maxValue*Math.random());}return arr;}public static int[] copyArr(int[] arr){int[] help = new int[arr.length];for (int i = 0; i < help.length; i++) {help[i] = arr[i];}return help;}public static void main(String[] args) {//int[] arr = {96,4,12,6,1,15,-1,7,5};//mergesort(arr);//rocessCircle(arr);int maxSize = 100;int maxValue = 100000;int test = 1000;boolean isTrue = true;for (int i = 0; i < test; i++) {int[] arr = generateRandomArray(maxSize,maxValue);int[] help = copyArr(arr);if(arr == null || arr.length < 2){continue;}//System.out.println(arr.length);mergesort(arr);processCircle(help);for (int j = 0; j < arr.length; j++) {if(arr[j] != help[j]){isTrue = false;break;}}if(!isTrue){break;}}if(isTrue){System.out.println("一致");}else{System.out.println("異常");}} }

總結

以上是生活随笔為你收集整理的数据结构与算法:归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。