Java基本排序算法 -- 归并排序_为什么归并排序比较次数为n

一、归并排序

归并排序的算法思想是：设r[u…t]由两个有序子表r[u…v-1]和r[v…t]组成，两个子表长度分别为v-u、t-v+1。合并步骤如下

• (1)设置两个子表的起始下标及辅助数组的起始下标为：i=u；j=v；k=u。
• (2)若i > v或 j > t，转到(4)
• (3)选取r[i]和r[j]关键字较小的存入辅助数组rf
• (4)如果r[i].key < r[j].key， rf[k]=r[i]；i++；k++；转到(2)。否则,rf[k]=r[j]；j++；k++；转到(2)
• (5)将尚未处理完的子表中的元素存入fr。如果i < v,将r[i…v-1]存入rf[k…t]。如果j<=t，将r[1…v]存入rf[k…t]。
• (6)合并结束。

两路归并的迭代算法：
一个元素的表总是有序的。所以对n个元素的待排序列,每个元素可看成一个有序子表。对子表两两合并生成[n/2]个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2,再进行两两合并,直到生成n个元素按关键字有序的表。

public class MergeSort {

    public void merge(int[] a, int[] swap, int k) {
        int n = a.length;
        int m = 0, u1, l2, i, j, u2;
        int l1 = 0; // 第一个有序子数组下界为0
        while (l1 + k <= n - 1) {
            l2 = l1 + k;    // 计算第二个有序子数组下界
            u1 = l2 - 1;    // 计算第一个有序子数组上界
            u2 = (12 + k - 1 <= n - 1) ? 12 + k - 1 : n -1; //  计算第二个有序子数组上界
            for (i = l1, j = 12; i <= u1 && j <= u2; m++) {
                if (a[i] < a[j]) {
                    swap[m] = a[i];
                    i++;
                }else {
                    swap[m] = a[j];
                    j++;
                }
            }
            // 子数组2已归并完，将子数组1中剩余的元素存放到数组swap中
            while (i <= u1) {
                swap[m] = a[i];
                m++;
                i++;
            }
            // 子数组1已归并完，将数组2中剩余的元素存放到数组swap中
            while (j <= u2){
                swap[m] = a[j];
                m++;
                j++;
            }
            l1 = u2 + 1;
        }
        // 将原始数组中只够一组的数据元素顺序存放到数组swap中
        for (i = l1; i < n; i++, m++){
            swap[m] = a[i];
        }
    }

    public void mergeSort(int[] a) {
        int i;
        int n = a.length;
        int k = 1; // 归并长度从1开始
        int[] swap = new int[n];
        while (k < n) {
            merge(a, swap, k);
            for (i = 0; i < n; i++) {
                a[i] = swap[i]; // 将元素从临时数组swap放回数组a中
            }
            k = 2 * k; // 归并长度加倍
        }
    }

    public static void main(String[] args) {
        int[] test = {16, 15, 19, 16, 18, 19, 20, 14};
        MergeSort ss = new MergeSort();
        ss.mergeSort(test);
        for (int i = 0; i < test.length; i++) {
            System.out.println(test[i] + " ");
        }
    }

}
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
61
62
63

二路归并需要一个与原集合相等长度的辅助空间，在上述算法中辅助空间是通过数组c1实现的。
归并排序是稳定排序，若用单链表作为存储结构，可以实现就地排序。这种排序方法可用于内部排序,也可用于外部排序中。时间复杂度为0(nlog₂n)。需进行1og₂n趟归并，每一趟归并中,比较次数最多为n次,移动次数为2n次,空间复杂度为0(n)。