Java排序算法三之归并排序的递归与非递归的实现示例解析
归并有递归和非递归两种。
归并的思想是:
1.将原数组首先进行两个元素为一组的排序,然后合并为四个一组,八个一组,直至合并整个数组;
2.合并两个子数组的时候,需要借助一个临时数组,用来存放当前的归并后的两个数组;
3.将临时数组复制回原数组对应的位置。
非递归的代码如下:
packagemergesort; importjava.util.Arrays; importjava.util.Random; importjava.util.Scanner; //归并排序的非递归算法 publicclassMergeSort{ publicstaticvoidmain(Stringargs[]){ MergeSortmer=newMergeSort(); int[]array=mer.getArray(); System.out.println("OriginalArray:"+Arrays.toString(array)); mer.mergeSort(array); System.out.println("SortedArray:"+Arrays.toString(array)); } publicint[]getArray(){ Scannercin=newScanner(System.in); System.out.print("InputthelengthofArray:"); intlength=cin.nextInt(); int[]arr=newint[length]; Randomr=newRandom(); for(inti=0;i递归算法的实现代码如下:
packagemergesort; publicclassMergeSort{ publicstaticvoidmergeSort(int[]data,intleft,intright){//left,right均为数字元素下标 if(left归并排序的时间复杂度为O(n*log2n),空间复杂度为O(n)
归并排序是一种稳定的排序方法。
到此这篇关于Java排序算法三之归并排序的递归与非递归的实现示例解析的文章就介绍到这了,更多相关Java排序算法之归并排序的递归与非递归内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票!