合并排序有在大二的《数据结构》课中出现过. 这篇博客讲的很详细.
上面这个人的博客讲的非常的好, 如果有打算看博客的可以经常关注.
将他的简化得到如下:
(图片引自上述博客)
简言之, 就是利用分治的思想将数组划分为 (n/log n) 段(log n 为划分层次), 然后合并多个有序数组.
上代码:
- public class a_2_7 <T extends Comparable>{
- /*
- * 对数组进行划分
- * */
- public static<T extends Comparable> void divide(T a[],int left,int right){
- /* 2, 如果数组无法划分了就直接返回 */
- if(a==null||left>=right) return ;
- /* 1, 对数组进行划分, 依据 mid 进行划分 */
- int mid=(left+right)/2;
- divide(a,left,mid);
- divide(a,mid+1,right);
- /* 3, 对数组进行合并 */
- merge(a,left,mid,right);
- /* 8, 合并完成 */
- }
- public static<T extends Comparable> void merge(T [] a, int left, int mid, int right) {
- /* 4, 新建临时存储区 */
- Object []temp=new Object[right-left+1];
- int i=left,j=mid+1,k=0;
- /* 5, 将当前分段的左右两边进行合并 */
- while(i<=mid&&j<=right){
- if(a[i].compareTo(a[j])<=0)temp[k++]=a[i++];
- else temp[k++]=a[j++];
- }
- /* 6, 合并剩余未合并完成的段 */
- while(i<=mid)temp[k++]=a[i++];
- while(j<=right)temp[k++]=a[j++];
- /* 7, 将临时存储区的内容复制到原始数组中 */
- k=0;
- for(Object o : temp){
- a[k+left]=(T)temp[k];
- k++;
- }
- }
- public static void main(String []args){
- Integer []a=new Integer[100];
- for(int i=0;i<a.length;++i)a[i]=100-i;
- for(Integer i : a) System.out.print(i+" ");
- System.out.println();
- divide(a,0,a.length-1);
- for(Integer i : a) System.out.print(i+" ");
- }
- }
运行结果如下:
上述代码注释基本描述清楚了内容.
在写这几次的代码过程中, 发现了一个问题, 自己的 Java 内容忘得差不多了, 而且泛型接触的很少, 后面再做 Java 泛型的博客.
2_7 递归与分治策略(合并排序)
来源: http://www.bubuko.com/infodetail-2971632.html