锁定老帖子 主题:排序算法---归并排序
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-10-07
归并排序中的“归并”的意思是将两个或者两个以上的有序表组合成一个新的有序表。他的实现无论是顺序存储结构还是链表结构,都可以在O(m+n)的时间级上实现。
复杂度: 时间复杂度:O(nlogn) 空间复杂度:O(n)
用途: 1、排序(速度仅次于快速排序,但较稳定) 2、求逆序对数
在实现单数组的归并排序之前,首先了解一下双数组的归并排序 这个双数组归并的前提是两个数组a和b都是已经排序好的
package sort; import java.util.Arrays; public class Test1 { public static void main(String args[]) { int a[]={1,2,3,4,6,7,8,10}; int b[]={1,2,5,9}; int c[] = new int[a.length+b.length]; mergeSort(a,a.length,b,b.length,c); System.out.println(Arrays.toString(c)); } public static void mergeSort(int a[],int n,int b[],int m,int c[]) { int i,j,k; i=j=k=0; //只有满足i<n&&j<m才执行,分别扫描两个数组,将数组中的元素进行对比,从小到大赋值给临时数组c while(i<n&&j<m) { if(a[i]<b[j]) c[k++]=a[i++]; else c[k++]=b[j++]; } //将剩余的a数组的元素放入c中 while(i<n) { c[k++]=a[i++]; } //将剩余的b数组的元素放入c中 while(j<m) { c[k++]=b[j++]; } } } 运行结果如下: [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]
下面开始实现单数组的归并排序算法 例如:49 38 65 97 76 13 27 思想:首先将数组中个单独的一个元素作为一个已经排序好的序列,然后,将两两相邻的元素进行归并排序,依次类推,直到最后归并为一个排序好的序列
首先将每个元素作为一个已经排序好的序列,一共7个序列 然后,将每两个相邻的序列归并为一个序列,如49 38归并排序后变成 38 49,依次分成了4个序列,然后再将之前已经排序好的两个相邻的序列进行排序,变成2个序列,每个序列都是排序好的,最后归并为一个排序好的序列
实现代码:
package sort; import java.util.Arrays; public class MergeSort { public static void main(String args[]) { int[] array = {49,38,65,97,76,13,27}; System.out.println(Arrays.toString(array)); System.out.println("---------排序前-------------"); mergeSort(array,0,array.length-1); System.out.println("---------排序后-------------"); System.out.println(Arrays.toString(array)); } /** * 这里依然需要递归来达到数组元素的排序,如果有两个已有元素的数组的话,就不用这么麻烦您了 * 不过这种归并排序依然是效率最好的排序方法之一,而且还是稳定的(相比快速排序,快速排序不稳定) */ public static void mergeSort(int array[],int low,int high) { if(low<high) { mergeSort(array,low,(low+high)/2);//左边排序 mergeSort(array,(low+high)/2+1,high);//右边排序 merge(array,low,(high+low)/2,high);//将两个序列归并为一个序列 System.out.println(Arrays.toString(array)); } } public static void merge(int array[],int low,int mid,int high) { int temp[]=new int[high-low+1]; int i = low; int j = mid+1; int k=0; /** * 将array数组分成两个数组来扫描,每一次都会将前后相邻的两个有序的序列归并为一个有序的序列 */ while(i<=mid&&j<=high) { if(array[i]<=array[j]) temp[k++]=array[i++]; else temp[k++]=array[j++]; } //下面这两种while循环每次只执行其中一个 //将剩余的array[i]存入temp中 while(i<=mid) { temp[k++]=array[i++]; } //将剩余的array[j]存放到temp中 while(j<=high) { temp[k++]=array[j++]; } for(int m=0;m<temp.length;m++) { array[low+m]=temp[m]; } } } 运行结果如下:
[49, 38, 65, 97, 76, 13, 27] ---------排序前------------- [38, 49, 65, 97, 76, 13, 27] [38, 49, 65, 97, 76, 13, 27] [38, 49, 65, 97, 76, 13, 27] [38, 49, 65, 97, 13, 76, 27] [38, 49, 65, 97, 13, 27, 76] [13, 27, 38, 49, 65, 76, 97] ---------排序后------------- [13, 27, 38, 49, 65, 76, 97] 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
浏览 2023 次