算法-归并排序

Posted on | In |

介绍

将两个有序数列合并成一个有序数列

根据实现方式分为“从上往下”和“从下往上”两种方式

分析图使用的graphviz

从下往上（非递归实现）

分析

将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止

归并排序从下到上3

c实现
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/**
 合并两个有序数组

 @param a 原数组
 @param low 起始位
 @param mid 中间位
 @param high 终点位
 */
void merge(int a[], int low, int mid, int high)
{
    //申请临时合并区域
    int *temp = (int *)malloc(sizeof(int) * (high - low + 1));
    int i = low;
    int j = mid + 1;
    int k = 0;
    
    //合并左右区间
    while (i <= mid && j <= high) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        }
        else {
            temp[k++] = a[j++];
        }
    }
    
    //合并剩余左区间
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    
    //合并剩余右区间
    while (j <= high) {
        temp[k++] = a[j++];
    }
    
    //临时区域数组整合到原数组
    for (int i = 0; i < k; i++) {
        a[low + i] = temp[i];
    }
    
    free(temp);
}

/**
 数组合并

 @param a 原数组
 @param len 数组长度
 @param subLen 子数组长度
 */
void mergeGroups(int a[], int len, int subLen)
{
    int i = 0;
    //没2个相邻的子数组进行合并排序
    for (i = 0; i + 2 * subLen - 1 < len; i += (2 * subLen)) {
        merge(a, i, i + subLen - 1, i + 2 * subLen - 1);
    }
    
    //若i + subLen - 1 < len - 1，则剩余一个子数组未配对
    if (i + subLen - 1 < len - 1) {
        merge(a, i, i + subLen - 1, len - 1);
    }
}


/**
 归并排序 从下到上

 @param a 原数组
 @param len 数组长度
 */
void mergeSortDownToUp(int a[], int len)
{
    if (a == NULL || len <= 0) {
        return;
    }
    
    for (int i = 1; i < len; i *= 2) {
        mergeGroups(a, len, i);
    }
}

/**
 测试归并排序
 */
void testMergeSort()
{
    int arr[8] = { 19, 3, 10, 9, 16, 11, 28, 26 };
    int len = sizeof(arr)/ sizeof(arr[0]);
    
    printf("归并排序前:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    
    //从上到下
//    mergeSortUpToDown(arr, 0, len - 1);
    //从下到上
    mergeSortDownToUp(arr, len);
    
    printf("\n归并排序后:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
Swift实现
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/// 合并两个有序数组
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - low: 起始位
    ///   - mid: 中间位
    ///   - high: 终点位
    func merge(a: inout [Int], low: Int, mid: Int, high: Int) {
        var temp: [Int] = [Int]()
        var i = low
        var j = mid + 1
        
        while i <= mid && j <= high {
            if a[i] <= a[j] {
                temp.append(a[i])
                i += 1
            }
            else {
                temp.append(a[j])
                j += 1
            }
        }
        
        while i <= mid {
            temp.append(a[i])
            i += 1
        }
        
        while j <= high {
            temp.append(a[j])
            j += 1
        }
        
        for i in 0..<temp.count {
            a[low + i] = temp[i]
        }
    }
    
/// 数组合并
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - len: 数组长度
    ///   - subLen: 子数组长度
    func mergeGroups(a: inout [Int], len: Int, subLen: Int)
    {
        var i = 0
        for index in stride(from: 0, to: len - 2 * subLen + 1, by: 2 * subLen) {
            i = index
            merge(a: &a, low: index, mid: index + subLen - 1, high: index + 2 * subLen - 1)
        }
        
        if i + subLen - 1 < len - 1 {
            merge(a: &a, low: i, mid: i + subLen - 1, high: len - 1)
        }
    }

    /// 归并排序 从下到上
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - len: 数组长度
    func mergeSortDownToUp(a: inout [Int], len: Int)
    {
        if a.isEmpty || len <= 0 {
            return;
        }

        var i = 1;
        for _ in 1..<len {
            if i < len {
                mergeGroups(a: &a, len: len, subLen: i)

            }
            else {
                break
            }
            i *= 2;
        }
    }
    
    /// 测试归并排序
    func testMergeSort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("归并排序前:\(arr)", separator: " ")
//        mergeSortUpToDown(a: &arr, low: 0, high: arr.count - 1)
        mergeSortDownToUp(a: &arr, len: arr.count)
        print("归并排序后:\(arr)", separator: " ")
    }

从上往下（递归实现）

分析

分解: 将当前区间一分为二，及中间点 mid = (low + high) / 2
求解: 递归对左区间[low…mid]和右区间[mid + 1…high]进行递归排序。递归的结束条件是子区间长度为1
合并: 将已排序的左区间[low…mid]和右区间[mid + 1…high]归并为一个有序区间[low…high]

归并排序从上到下

C实现
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 合并两个有序数组

 @param a 原数组
 @param low 起始位
 @param mid 中间位
 @param high 终点位
 */
void merge(int a[], int low, int mid, int high)
{
    //申请临时合并区域
    int *temp = (int *)malloc(sizeof(int) * (high - low + 1));
    int i = low;
    int j = mid + 1;
    int k = 0;
    
    //合并左右区间
    while (i <= mid && j <= high) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        }
        else {
            temp[k++] = a[j++];
        }
    }
    
    //合并剩余左区间
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    
    //合并剩余右区间
    while (j <= high) {
        temp[k++] = a[j++];
    }
    
    //临时区域数组整合到原数组
    for (int i = 0; i < k; i++) {
        a[low + i] = temp[i];
    }
    
    free(temp);
}


/**
 归并排序 从上到下（分而治之） 采用分解->求解->合并

 @param a 原数组
 @param low 起始位
 @param high 终点位
 */
void mergeSortUpToDown(int a[], int low, int high)
{
    if (a == NULL || low >= high) {
        return;
    }
    
    int mid = (low + high) / 2;
    mergeSortUpToDown(a, low, mid);
    mergeSortUpToDown(a, mid + 1, high);
    
    merge(a, low, mid, high);
}

/**
 测试归并排序
 */
void testMergeSort()
{
    int arr[8] = { 19, 3, 10, 9, 16, 11, 28, 26 };
    int len = sizeof(arr)/ sizeof(arr[0]);
    
    printf("归并排序前:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    
    //从上到下
    mergeSortUpToDown(arr, 0, len - 1);
    //从下到上
    //mergeSortDownToUp(arr, len);
    
    printf("\n归并排序后:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
Swift实现
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
64
65
/// 合并两个有序数组
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - low: 起始位
    ///   - mid: 中间位
    ///   - high: 终点位
    func merge(a: inout [Int], low: Int, mid: Int, high: Int) {
        var temp: [Int] = [Int]()
        var i = low
        var j = mid + 1
        
        while i <= mid && j <= high {
            if a[i] <= a[j] {
                temp.append(a[i])
                i += 1
            }
            else {
                temp.append(a[j])
                j += 1
            }
        }
        
        while i <= mid {
            temp.append(a[i])
            i += 1
        }
        
        while j <= high {
            temp.append(a[j])
            j += 1
        }
        
        for i in 0..<temp.count {
            a[low + i] = temp[i]
        }
    }
    
    
    /// 归并排序 从上到下（分而治之） 采用分解->求解->合并
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - low: 起始位
    ///   - high: 终点位
    func mergeSortUpToDown(a: inout [Int], low: Int, high: Int) {
        if a.isEmpty || low >= high {
            return;
        }
        
        let mid = (low + high) / 2;
        mergeSortUpToDown(a: &a, low: low, high: mid);
        mergeSortUpToDown(a: &a, low: mid + 1, high: high);
        
        merge(a: &a, low: low, mid: mid, high: high)
    }
    
        /// 测试归并排序
    func testMergeSort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("归并排序前:\(arr)", separator: " ")
        //mergeSortUpToDown(a: &arr, low: 0, high: arr.count - 1)
        mergeSortDownToUp(a: &arr, len: arr.count)
        print("归并排序后:\(arr)", separator: " ")
    }

总结

时间复杂度:

  • 最差O(nlogn)

  • 最优O(nlogn)

  • 平均O(nlogn)

空间复杂度:

  • O(n)

稳定性:

  • 稳定

参考

graphviz程序员画图

graphviz使用说明