数据结构与算法-归并排序教程版

  • 2

数据结构与算法-归并排序

原理介绍

归并排序 其实思想很简单,如上图,就是将待排序数组,分成若干个小数组,将最终的两个数据排序后,在进行合并。简而言之,就是分而治之的思想。将一个大问题,分成若干个小问题来解决,小问题解决了之后,随之大问题也就会迎刃而解。其实分治思想跟递归思想很相像,分析递推公式,找到终止条件,然后根据这个思路进行编码。

代码实现

归并排序的主方法,将待排序数据以及大小传递到核心排序算法方法中。

 // 归并排序算法, a是数组,n表示数组大小
    public static void mergeSort(int[] a, int n) {
        mergeSortInternally(a, 0, n - 1);
    }

如下的递归函数方法,首先是判断终止条件,如果递归调用到数组的最后一位,就会终止调用。我们可以很清楚的看到代码第9、10行是将当前数组分割为两个范围来进行排序,然后进行递归调用当前方法,其实现逻辑就是上面归并排序图的步骤。

 // 递归调用函数
    private static void mergeSortInternally(int[] a, int p, int r) {
        // 递归终止条件
        if (p >= r) return;

        // 取p到r之间的中间位置q,防止(p+r)的和超过int类型最大值
        int q = p + (r - p) / 2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q + 1, r);

        // 将A

和A[q+1...r]合并为A

merge(a, p, q, r); }

最后,我们来看下merge这个方法,它其实就是将最终排好序的数据合并成一个有序的数组,并且放入int[] a当中。
具体过程就是,我们申请一个临时数组,与原数组空间已知,使用两个变量ij,它俩分别指向p和p+1的第一个元素,然后循环当前数据下标,直到数组对比完毕。比较的过程就是如果a[i] <= a[j]时,将a[i]放入临时数组中,并且i后移一位,否则将a[j]放入临时数组中,并且j后移一位。循环对比,直到其中一个数组中的数据都放入了临时数组当中,再将另一个数组中的数据追加到第一个数组末尾,这个时候两个已排序后的数据就合并完成了。最后将临时数组中的数据拷贝到int a[]数组中即可。

 // 递归调用函数
    private static void mergeSortInternally(int[] a, int p, int r) {
        // 递归终止条件
        if (p >= r) return;

        // 取p到r之间的中间位置q,防止(p+r)的和超过int类型最大值
        int q = p + (r - p) / 2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q + 1, r);

        // 将A

和A[q+1...r]合并为A

merge(a, p, q, r); } private static void merge(int[] a, int p, int q, int r) { int i = p; int j = q + 1; int k = 0; // 初始化变量i, j, k int[] tmp = new int[r - p + 1]; // 申请一个大小跟a

一样的临时数组 while (i <= q && j <= r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; // i++等于i:=i+1 } else { tmp[k++] = a[j++]; } } // 判断哪个子数组中有剩余的数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 将剩余的数据拷贝到临时数组tmp while (start <= end) { tmp[k++] = a[start++]; } // 将tmp中的数组拷贝回a

for (i = 0; i <= r - p; ++i) { a

= tmp[i]; } }

测试结果

最后写一个测试方法来测试归并排序算法,如下

 int[] mergeSort = {11, 8, 3, 9, 7, 1, 2, 5};
        mergeSort(mergeSort, mergeSort.length);
        for (int i = 0; i < mergeSort.length; i++) {
            System.out.print(mergeSort[i] + " ");
        }

最终排序结果为1 2 3 5 7 8 9 11