溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
Java排序算法三之歸并排序的遞歸與非遞歸的案例分析？這個問題可能是我們日常學習或工作經常見到的。希望通過這個問題能讓你收獲頗深。下面是小編給大家帶來的參考內容，讓我們一起來看看吧！
歸并有遞歸和非遞歸兩種。
歸并的思想是：
1.將原數組首先進行兩個元素為一組的排序，然后合并為四個一組，八個一組，直至合并整個數組；
2.合并兩個子數組的時候，需要借助一個臨時數組，用來存放當前的歸并后的兩個數組；
3.將臨時數組復制回原數組對應的位置。
非遞歸的代碼如下：
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++];
}
}
}遞歸算法的實現代碼如下：
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排序算法三之歸并排序的遞歸與非遞歸的案例分析大概了解了嗎？希望文章內容對大家有所幫助。如果想了解更多相關文章內容，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
