vlambda博客
学习文章列表

归并排序

思想

将需要排序的数据分为前后两个部分，然后对前后两个部分的数据分别进行排序，递归该操作，最后将排序的数据两两部分进行合并。这是分治的思想，将大问题分解为小的子问题来解决。

实现

利用递归来解决问题
递归公式
MergeSort(start, end) = merge(MergeSort(start,(start+end)/2), MergeSort((start+end)/2 + 1, end))
递归终止条件
start >= end

具体过程

用i和j，分别指向两个待merge数组（arr）的第一个元素，比较对应位置上的大小，如果arr[i]<arr[j]，那么将小的数字放入到一个新的数组tmp中，然后i向后移动一位，否则将大的放入tmp，j往后移动一位。重复以上过程，直到有一个数组空了，那么将另外一个子数组中的数据追加到tmp的尾部。

具体代码

public static void main(String[] args){
 int[] nums = {6,5,23,53,65,276,9};//测试数据
 mergeSort(nums);
}
public static void mergeSort(int[] arr){
 if(arr==null || arr.length<2){//如果只有一个或者没有 那么可以直接返回
        return;
    }
    mergeSort(arr, 0, arr.length-1);
}
public static void mergeSort(int[] arr, int left, int right){
    if(left==right){//递归的终止条件
        return;
    }
    int mid = left+((right-left)>>1);
    mergeSort(arr, left, mid);//左边
    mergeSort(arr, mid+1, right);//右边
    merge(arr, left, mid, right);//合并
}
public static void  merge(int[] arr ,int left, int mid, int right){
    int[] tmp = new int[right-left+1];//创建临时数组来存
    int i=0;//第一个元素
    int p1=left;//左边起点，第一个数字
    int p2=mid+1;//右边起点，第一个数字
    while(p1<=mid&&p2<=right){
        tmp[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];//先对左右数据进行遍历，遇到小的存放进临时空间
    }
    while(p1<=m){
        tmp[i++]=arr[p1++];//若还有剩余，那么直接存放
    }
    while(p2<=r){
        tmp[i++]=arr[p2++];//若还有剩余，那么直接存放
    }
    for(i=0;i<temp.length;i++){
        arr[left+i]=tmp[i];//覆盖原来的数组
    }
}

时间复杂度

时间复杂度为O(nlogn)，时间复杂度是稳定的。

分析过程：

• 递归第一层：将n个数划分为2个子区间，那么每个子区间的数字个数为n/2；

• 递归第二层：将n个数划分为4个子区间，那么每个子区间的数字个数为n/4；

• 递归第三层：将n个数划分为8个子区间，那么每个子区间的数字个数为n/8；

  ……

• 递归第logn层：将n个数划分为n个子区间，那么每个子区间的数字个数为1；

接下来要进行合并，对相邻的两个子区间进行合并，过程如下：

• 在logn层，每两个子取件进行合并，总共合并n/2次。n个数字都会被遍历，时间复杂度为O(n);

  ……

• 在第二层，每个子区间长度为n/4，总共有4个子区间，每两个相邻子区间进行合并，总共合并2次。n个数字都会被遍历，时间复杂度为O(n)；

• 在第二层，每个子区间长度为n/2，总共有2个子区间，每两个相邻子区间进行合并，总共合并1次。n个数字都会被遍历，时间复杂度为O(n)；

通过上面的过程我们可以发现，对于每一层来说，在合并所有子区间的过程中，n个元素都会被操作一次，所以每一层的时间复杂度都是O(n)。而之前我们说过，归并排序划分子区间，将子区间划分为只剩1个元素，需要划分logn次。每一层的时间复杂度为O（n），共有logn层，所以归并排序的时间复杂度就是O(nlogn)。

非递归

public static void main(String[] args) {
    int[] nums = {6, 5, 3, 8, 1, 7, 2, 9, 4};
    for (int i = 1; i <= nums.length; i *= 2) {
        for (int j = 0; j + i <= nums.length; j += i * 2) {//最开始是两两合并，后面控制i进行44合并……
            //Math.min 的目的是处理 整个待排序数组为奇数的情况
            merge(nums, j, j + i - 1, Math.min(j + 2 * i - 1, nums.length - 1));
        }
    }
    System.out.println(Arrays.toString(nums));
}

/**
 * 两两归并排好序的数组（2路归并）
 *
 * @param nums   带排序数组对象
 * @param left   左边数组的第一个索引
 * @param center 左数组的最后一个索引，center + 1右数组的第一个索引
 * @param right 右数组的最后一个索引
 */
private static void merge(int[] nums, int left, int center, int right) {
    int[] tmpArray = new int[right - left + 1];
    int leftIndex = left;   //左数组第一个元素的索引
    int rightIndex = center + 1;   //右数组第一个元素索引
    int tmpIndex = 0;    //临时数组索引

    // 把较小的数先移到新数组中
    while (leftIndex <= center && rightIndex <= right) {
        if (nums[leftIndex] <= nums[rightIndex]) {
            tmpArray[tmpIndex++] = nums[leftIndex++];
        } else {
            tmpArray[tmpIndex++] = nums[rightIndex++];
        }
    }

    // 把左边剩余的数移入数组
    while (leftIndex <= center) {
        tmpArray[tmpIndex++] = nums[leftIndex++];
    }

    // 把右边边剩余的数移入数组
    while (rightIndex <= right) {
        tmpArray[tmpIndex++] = nums[rightIndex++];
    }

    // 把新数组中的数覆盖nums数组
    /*for (int i = 0; i < tmpArray.length; i++) {
        nums[begin + i] = tmpArray[i];
    }*/
    //可以优化成下面的写法
    System.arraycopy(tmpArray, 0, nums, left, tmpArray.length);
}

应用场景

外排序是指处理超过内存限度的数据的排序算法。通常将中间结果放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用排序-归并"策略

• 排序阶段:读入能放在内存中的数据量，将其排序输出到临时文件，一次进行，将待排序数据组织为多个有序的临时文件。

• 归并阶段:将这些临时文件组合为大的有序文件。

【举例】

• 使用100M内存对于900MB的数据进行排序:

• 读入100M数据内存，用常规方式(如堆排序)排序。。将排序后的数据写入磁盘。

• 重复前两个步骤，得到9个100MB的块( 临时文件)中。

• 将100M内存划分为10份，前9份中为输入缓冲区，第10份输出缓冲区。

  (如前9份各8M，第10份18M;或10份大小同时为10M)

• 执行九路归并算法，将结果输出到缓冲区(若输出缓冲区满，将数据写至目标文件，清空缓冲区。若输入缓冲区空，读入相应文件的下一份数据)

总结

1.归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2.时间复杂度:O(NlogN)

3.空间复杂度:O(N)

4.稳定性:稳定

参考链接

[1]https://blog.csdn.net/weixin_39962199/article/details/111096015

[2]https://www.cnblogs.com/jing-yi/p/13204160.html

[3]https://www.cnblogs.com/acm-bingzi/p/mergesort.html