程序员社区

【数据结构与算法】归并排序

归并排序的原理

归并排序的思想是如果要排序一个数组,需要把数组分为两部分,然后对两部分分别进行排序,再将排序好的数组合并起来。归并排序其实分为两个步骤,先进行待排数据的分解,再对最小集进行排序,在进行合并。

归并排序其实就是一个分治的思想,分一般采用的形式是递归来解决的,而治在这里指的是把各阶段的答案拼在一起。

【数据结构与算法】归并排序插图

归并排序的伪代码

第一个方法{
创建一个和原数组一样大的临时数组。
调用第二个方法,参数为0,数组长度-1,原数组,临时数组temp
}

第二个方法
{
递归的出口是数组的长度为1。
对待排序数组进行二分,分为左分区,和右分区。
递归的进行切分下去
对左分区和右分区进行merge操作,合并数组。merge方法传入的参数为:待排序区间的边界索引(三个),原数组,临时数组
}

第三个方法merge{
遍历待排区间,依次比较左区间右区间的数的大小,小的数放到临时区间中,直到某个区间遍历完成
遍历未遍历完的剩余区间的数,依次追加到临时数组。
拷贝临时数组至原数组中。
}

代码示例

public class MergeSort {
    public static void main(String[] args){
        int a[] = {9,8,7,6,5,4,3,2,1,0};
        mergeSort(a);
        System.out.println("ok:" + Arrays.toString(a));
    }

    public static void mergeSort (int[] num){
        if(num==null || num.length==1){
            return;
        }
        int[] temp = new int[num.length];
        sort(num,temp,0,num.length-1);

    }

    public static void sort(int[] num,int[] temp,int left,int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        sort(num,temp,left,mid);
        sort(num,temp,mid+1,right);

        merge(num,temp,left,mid,right);
        System.out.println(Arrays.toString(num));
    }

   public static void merger(int[] arr,int[] temp,int left,int mid,int right){
        int k = left;
        int l = left;
        int r = mid+1;

        while(l<=mid && r<=right){
            if(arr[l]<=arr[r]){
                temp[k++]=arr[l++];
            }else{
                temp[k++]=arr[r++];
            }
        }

        while (l <= mid) {  // 左边如果有剩余
            temp[k++] = arr[l++];
        }
        while (r <= right) { // 右边如果有剩余
            temp[k++] = arr[r++];
        }

        for(int i = left;i<=right;i++){
            arr[i]=temp[i];
        }

    }
}

性能分析

最佳情况:T(n) = O(n)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)
对于长度为 N 的任意数组,自顶向下的归并排序需要 1/2NlgN - NlgN 次比较。
对于长度为 N 的任意数组,自顶向下的归并排序最多需要访问数组 6NlgN 次(2N 次用来复制、2N 次用来将排好序的元素移动回来、另外最多比较 2N 次)。

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【数据结构与算法】归并排序

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区