排序算法之归并排序迭代实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之归并排序迭代实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1889字，纯文字阅读大概需要3分钟。

内容图文

快要过节了，目前先把代码贴上，后续加上图示和复杂度信息

package com.jdk8.event.SortTest;

public class MergeSortIterate {
    public static void main(String[] args){
        int[] arrs = {2,7,15,30,28,5,43,66,52,86,79};
        System.out.println("归并排序前:");
        display(arrs);
        mergeSort(arrs);
        System.out.println("归并排序后:");
        display(arrs);
    }

    public static void mergeSort(int[] arrs) {
        int[] temp = new int[arrs.length];//临时空间，用于存放归并结果
        int squa = 1;//子序列起始长度为1
        while(squa < arrs.length){
            mergeDownToUp(arrs,temp,squa,arrs.length);
            squa = 2 * squa;
        }
    }

    public static void mergeDownToUp(int[] arrs, int[] temp, int squa, int length) {
        int left = 0,middle,right;

        while (left < length -2*squa + 1){//即right<length  length-right = length-2*squa+1 > left
            right = left + 2*squa -1;
            middle = (left + right)/2;
            merge(arrs,temp,left,middle,right);
            left = left + 2*squa;
        }

        //处理剩下的尾数
        if(left < length - squa + 1){ //即middle<length 推导(length -middle = length - squa + 1 > left)
            merge(arrs,temp,left,left+squa-1,length-1);
        }else{
            while(left < length){
                if(temp[left] != arrs[left]){
                    temp[left] = arrs[left];
                }
                left = left + 1;
            }
        }
    }

    public static void merge(int[] arrs, int[] temp, int start, int middle, int end) {
        int i = start,t = start,j = middle + 1;
        while (i <= middle && j<=end){
            if(arrs[i] <= arrs[j]){
                temp[t] = arrs[i];
                t = t + 1;
                i = i + 1;
            }else{
                temp[t] = arrs[j];
                t = t + 1;
                j = j + 1;
            }
        }

        while (i <= middle){//将剩余的复制到temp
            temp[t] = arrs[i];
            t = t + 1;
            i = i + 1;
        }

        while (j <= end){//将剩余的复制到temp
            temp[t] = arrs[j];
            t = t + 1;
            j = j + 1;
        }
        while (start <= end){//将temp的数据覆盖arrs的数据
            if (arrs[start] != temp[start]){
                arrs[start] = temp[start];
            }
            start = start + 1;
        }
    }

    public static void display(int[] arrs){
        for(int i = 0;i < arrs.length;i++){
            System.out.print(" " + arrs[i] + " ");
        }
        System.out.println();
    }
}

运行结果如下:

归并排序前:
 2  7  15  30  28  5  43  66  52  86  79 
归并排序后:
 2  5  7  15  28  30  43  52  66  79  86 

内容总结

以上是互联网集市为您收集整理的排序算法之归并排序迭代实现全部内容，希望文章能够帮你解决排序算法之归并排序迭代实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---