Please enable Javascript to view the contents

排序算法之归并排序

 ·  ☕ 2 分钟

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  1. 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  2. 自下而上的迭代;

一、排序步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

二、动画演示

merge_sort

三、代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package com.whoismy8023.learning.sort;

import java.util.Arrays;

/**
 * Created by SPPan on 2019/9/11.
 * <p>
 * 归并排序
 */
public class MergeSortLearning {

    public static void main(String[] args) {
        int[] arr = {1, -1, 2, -2, 3, 6, 5, 4};
        System.out.printf("排序前:%s \n", Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
        System.out.printf("排序后:%s \n", Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }
        // 中间索引
        int mid = (left + right) / 2;
        // 向左递归进行分解
        mergeSort(arr, left, mid, temp);
        // 向右递归进行分解
        mergeSort(arr, mid + 1, right, temp);
        // 合并
        merge(arr, left, mid, right, temp);
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 初始化左边序列的指针
        int l = left;
        // 初始化右边序列的指针
        int r = mid + 1;
        // 将数据复制到辅助数组
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }
        for (int i = left; i <= right; i++) {
            if (l > mid) {
                // 此处表示左边序列已经处理完成,将右边序列剩余的复制回来即可
                arr[i] = temp[r++];
            } else if (r > right) {
                // 此处表示右边序列已经处理完成,将左边序列剩余的复制回来即可
                arr[i] = temp[l++];
            } else if (temp[l] < temp[r]) {
                // 此处表示两边序列都还没处理完,且左边的数据小于右边
                arr[i] = temp[l++];
            } else {
                // 此处表示两边序列都还没处理完,且右边的数据小于右边
                arr[i] = temp[r++];
            }
        }
        System.out.printf("合并%d到%d后的结果:%s \n", left, right, Arrays.toString(arr));
    }
}

四、代码演示结果

1
2
3
4
5
6
7
8
9
排序前:[1, -1, 2, -2, 3, 6, 5, 4] 
合并0到1后的结果:[-1, 1, 2, -2, 3, 6, 5, 4] 
合并2到3后的结果:[-1, 1, -2, 2, 3, 6, 5, 4] 
合并0到3后的结果:[-2, -1, 1, 2, 3, 6, 5, 4] 
合并4到5后的结果:[-2, -1, 1, 2, 3, 6, 5, 4] 
合并6到7后的结果:[-2, -1, 1, 2, 3, 6, 4, 5] 
合并4到7后的结果:[-2, -1, 1, 2, 3, 4, 5, 6] 
合并0到7后的结果:[-2, -1, 1, 2, 3, 4, 5, 6] 
排序后:[-2, -1, 1, 2, 3, 4, 5, 6] 
目录