快捷導(dǎo)航

Java排序算法三之歸并排序的遞歸與非遞歸的實(shí)現(xiàn)示例解析

更新時(shí)間：2020年08月05日 16:54:25 作者：gavenyeah

這篇文章主要介紹了Java排序算法三之歸并排序的遞歸與非遞歸的實(shí)現(xiàn)示例解析，文章通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

歸并有遞歸和非遞歸兩種。

歸并的思想是：
1.將原數(shù)組首先進(jìn)行兩個(gè)元素為一組的排序，然后合并為四個(gè)一組，八個(gè)一組，直至合并整個(gè)數(shù)組；
2.合并兩個(gè)子數(shù)組的時(shí)候，需要借助一個(gè)臨時(shí)數(shù)組，用來(lái)存放當(dāng)前的歸并后的兩個(gè)數(shù)組；
3.將臨時(shí)數(shù)組復(fù)制回原數(shù)組對(duì)應(yīng)的位置。

非遞歸的代碼如下：

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;//歸并的前半部分?jǐn)?shù)組
 int j = i + len;
 int len_j = j +len;//歸并的后半部分?jǐn)?shù)組
 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也有可能超過(guò)數(shù)組長(zhǎng)度
  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++];
 }
 }
}

遞歸算法的實(shí)現(xiàn)代碼如下：

package mergesort;

public class MergeSort {
 public static void mergeSort(int[] data,int left,int right){ //left,right均為數(shù)字元素下標(biāo)
 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("數(shù)組排序前：");
 printArray(a);
 System.out.print("\n");
 mergeSort(a,0,a.length-1);
 System.out.print("歸并排序后：");
 printArray(a);
 }
}

歸并排序的時(shí)間復(fù)雜度為O(n*log2n),空間復(fù)雜度為O(n)

歸并排序是一種穩(wěn)定的排序方法。

到此這篇關(guān)于Java排序算法三之歸并排序的遞歸與非遞歸的實(shí)現(xiàn)示例解析的文章就介紹到這了,更多相關(guān)Java排序算法之歸并排序的遞歸與非遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: