首页 > 编程语言 > 详细

排序之归并排序

时间:2019-03-12 23:33:10      阅读:68      评论:0      收藏:0      [点我收藏+]

标签:string   bsp   tar   array   ont   nal   return   元素   结果   

归并排序算法思想: 
分而治之(divide - conquer);每个递归过程涉及三个步骤 
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作 
第三, 合并: 合并两个排好序的子序列,生成排序结果. 

第一、二步:

public static void mergeInternal(int[] arr,int low,int high) {
        if(low>=high) return;
        int mid = (high - low)/2+low;
        //左边小数组
        mergeInternal(arr, low, mid);
        //右边小数组
        mergeInternal(arr, mid+1, high);
        //合并
        merge(arr,low,mid,high);
    }

第三步:

public static void merge(int[] arr,int p,int q,int r) {
        int i = p;
        int j = q+1;
        //定义新数组tmp
        int[] tmp = new int[r-p+1];
        int k = 0;
        //将数组前半部分和后半部分按大小放在tmp数组中
        while(i<=q&&j<=r) {
            if(arr[i]>arr[j]) {
                tmp[k++] = arr[j++];
            }else {
                tmp[k++] = arr[i++];
            }
        }
        //记录当前i和q
        int start = i;
        int end = q;
        //判断后半部分是否全部加入tmp数组中,没有赋给分别将j和r赋给start和end
        if(j<=r) {
            start = j;
            end = r;
        }
        //把剩余元素放在tmp后即可
        while(start<=end) {
            tmp[k++] = arr[start++];
        }
        //将tmp数组值赋给原数组
        /*for(i = 0;i<r-p+1;i++) {
            arr[p+i] = tmp[i];
        }*/
        System.arraycopy(tmp, 0, arr, p, tmp.length);
    }

main函数:

public static void main(String[] args) {
        int[] arr = {11,8,3,9,7,1,2,5};
                System.out.println(Arrays.toString(arr));
        mergeInternal(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }    

运行结果:

[11, 8, 3, 9, 7, 1, 2, 5]
[1, 2, 3, 5, 7, 8, 9, 11]

排序之归并排序

标签:string   bsp   tar   array   ont   nal   return   元素   结果   

原文:https://www.cnblogs.com/duy666/p/10520272.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号