温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java排序算法三之归并排序的递归与非递归的案例分析

发布时间:2020-08-10 11:17:54 来源:亿速云 阅读:203 作者:小新 栏目:开发技术

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排序算法三之归并排序的递归与非递归的案例分析大概了解了吗?希望文章内容对大家有所帮助。如果想了解更多相关文章内容,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI