排序算法之归并排序

归并排序

归并排序就一种排序方法

归并排序

原理

并归排序的原理就是合并两个有序的序列为一个有序序列，怎么才能有两个有序的序列呢？我们用一张图来讲解归并排序：

我们可以看到，我们从左到右将一个序列一分为二、二分为四……直到所有序列中只有一个，然后合并，从右到左开始合并，如4和10先合并，组成[4,10]，[4,10]再和6合并组成[4,6,10]……那么用什么方法呢，当然是递归了，代码如下：

实现

public static void mergeSort(int[] num, int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        mergeSort(num, l, mid);
        mergeSort(num, mid + 1, r);
        merge(num, l, mid, r);
    }
}

public static void merge(int[] num, int l, int mid, int r) {
    int[] tmp = new int[r - l + 1];
    int i = l;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= r) {
        if (num[i] < num[j]) {
            tmp[index] = num[i];
            i++;
        } else {
            tmp[index] = num[j];
            j++;
        }
        index++;
    }
    while (i <= mid) {
        tmp[index] = num[i];
        i++;
        index++;
    }
    while (j <= r) {
        tmp[index] = num[j];
        j++;
        index++;
    }
    for (int k = 0; k < tmp.length; k++) {
        num[k + l] = tmp[k];
    }
}