个人中心
gpt4 book ai didi

Java排序算法三之归并排序的递归与非递归的实现示例解析

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 28 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java排序算法三之归并排序的递归与非递归的实现示例解析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

归并有递归和非递归两种.

归并的思想是： 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 。

最后此篇关于Java排序算法三之归并排序的递归与非递归的实现示例解析的文章就讲到这里了,如果你想了解更多关于Java排序算法三之归并排序的递归与非递归的实现示例解析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

28 4 0
文章推荐： iOS-GCD详解及简单使用
文章推荐： iOS中从网络获取数据的几种方法的比较
文章推荐： IOS 贝塞尔曲线（UIBezierPath）属性、方法整理
文章推荐： iOS项目的开发命名规范教程
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com