排序算法 --- 归并排序

一、排序思想

归并排序是采用分治算法,即将一个大问题切分成一些小问题然后递归求解。归并排序的图解如下:

image.png

分的过程简单,就是将数组拆开来,拆到每组只有一个元素为止。治的过程是怎么排序的呢?以最后一次治为例,即将4 5 7 81 2 3 6合并成最终的有序序列为例,看看如何实现。

  • 首先创建一个新的数组tempArr,长度为要进行“治”的两个数组长度之和;
  • 然后用i指向4,即第一个数组的最左边,j指向1,即第二个数组的最左边;
  • 发现41大,那么就将1存入tempArr,同时指针j后移;
  • 继续比较指针ij所指元素的大小,发现24小,将2存入tempArr,同时j继续后移;
  • 继续比较,将3存入tempArrj继续后移;
  • 此时发现64大,就将4存入tempArr,同时i后移;
  • 56小,将5存入tempArri继续后移;
  • 76大,将6存入tempArr,此时j已经处于最后了,不能后移了;
  • 接着就将i所指的剩余元素都存入tempArr,这个tempArr就是有序的了。

欢迎大家关注我的公众号 javawebkf,目前正在慢慢地将简书文章搬到公众号,以后简书和公众号文章将同步更新,且简书上的付费文章在公众号上将免费。


二、代码实现

1. 第一种方式:

这种方式很容易懂,我们先不是要拆分数组吗?那就拆呗,拆到什么时候为止呢?拆出来的数组只有一个元素了那就不用拆了。

  • 拆分:
public static int[] sort(int[] arr) {
    if (arr == null || arr.length == 1) {
        return arr;
    }
    // 拆分数组
    int mid = arr.length / 2; // 中间指针,利用该指针将数组拆分
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    // 调用合并方法,因为left和right可能可以再拆分,所以传进去的left和right再递归调用当前方法
    return merge(sort(left), sort(right));
}
  • 合并:该方法传入两个数组,对数组进行合并上面已经讲了思路,按照思路来写就好了:
public static int[] merge(int[] left, int[] right) {
    // 定义临时数组
    int[] tempArr = new int[left.length + right.length];
    // 定义两个指针
    int i = 0; // left的指针
    int j = 0; // right的指针
    // 进行合并操作
    for(int index=0; index < tempArr.length; index ++) {
        // 如果left的遍历完了,那么将right中的剩余元素全部依次放入tempArr中
        if (i >= left.length) {
            tempArr[index] = right[j];
            j++; // 指针后移
        } else if(j >= right.length) {
            // 如果right遍历完了,那么将left中剩余的元素全部依次放入tempArr中
            tempArr[index] = left[i];
            i++; // 指针后移
        } else if (left[i] < right[j]) {
            // 如果i所指的数更小,就将该数存入tempArr
            tempArr[index] = left[i];
            i++; // 指针后移
        } else {
            // 如果j所指的数大于等于i所指的数,就将j所指的数存入tempArr
            tempArr[index] = right[j];
            j++; // 指针后移
        }
    }
    return tempArr;
}

没错,这样就搞定了,这就是完全按照上面案例分析来做的,不过缺点就是,拆分的时候,是真正的拆除两个数组来了,会浪费空间,优点就是容易理解。

2. 第二种方式:

第二种方式就是不真正的将数组拆成两部分,而是通过一个中间索引mid,将数组标识成两部分。这样就不需要真正的拆分,不会浪费空间,但是代码相对来说更难理解。

  • 合并:先看合并部分,除了原始数组外,还有三个参数,leftmid构成左边的数组,mid+1right构成右边的数组,只要理解了这一点,下面的代码就容易理解了。
public static void merge(int[] arr, int left, int mid, int right) {
    // 定义临时数组
    int[] tempArr = new int[right - left + 1]; 
    int i = left; // 左边数组的指针
    int j = mid + 1; // 右边数组的指针
    int k = 0; // 临时数组的指针
    // 当左边数组和右边数组都还没遍历完的时候
    while(i <= mid && j <= right) {
        // 如果i所指的元素更小,就其放入tempArr,同时i后移
        if (arr[i] <= arr[j]) {
            tempArr[k++] = arr[i++];
        } else {
            // 如果j所指的更小,就将其放入tempArr,同时j后移
            tempArr[k++] = arr[j++];
        }
    }
    // 如果左边的数组还没遍历完,就将左边数组剩余元素依次放入tempArr中
    while (i <= mid) {
        tempArr[k++] = arr[i++];
    }
    // 如果右边的数组还没遍历完,就将右边数组剩余元素依次放入tempArr中
    while (j <= right) {
        tempArr[k++] = arr[j++];
    }
    // 将tempArr中排好序的添加到原数组中
    for(int x=0; x<tempArr.length; x++) {
        arr[left + x] = tempArr[x];
    }
}
  • 拆分:拆分到什么时候为止呢,如果leftright相等了,表示只有一个元素,那就不用拆了,否则就对左边和右边的都进行递归拆分,拆到不可再拆就合并。
public static void sort(int[] arr, int left, int right) {
    // 如果左指针和右指针相等,表示只有一个元素,那就不需要拆分了
    if (left == right) {
        return;
    }
    // 否则就进行拆分
    int mid = left + (right - left) / 2; // 找到中间值进行拆分
    // 对左边再进行拆分
    sort(arr, left, mid);
    // 对右边再进行拆分
    sort(arr, mid+1, right);
    // 进行合并
    merge(arr, left, mid, right);
}

经测试,对1000万个随机数进行排序,大概需要2秒,方式一和方式二时间上差不多,但是方式二可以省不少的内存,大家可以在执行的时候看看内存的占用情况。

下一篇
举报

扫码关注云+社区

领取腾讯云代金券