归并排序算法（二路）——C/C++

r囧r小猫 2022-01-17 01:35 252阅读 0赞

# 归并排序（二路） #

## 1. 算法思想 ##

归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

## 2. 实现原理 ##

2.1、申请一个和原始排序数组空间一样大的额外数组。
    2.2、定义归并初始长度 length。
    2.3、将数组分块。
    2.4、将分块数组进行排序，把数据存入额外一个数组。（下一次用额外数组排序，数据存入原始数组，轮流存储）
    2.5、增加归并长度 length*2。
    2.6、重复3-5步，即可得到排序。

## 3. 动态演示 ##

网上的和我的想法有点不一样  
网上动图都是依次分组，当有有序数组长度一样时归并排序，然后合并。  
![在这里插入图片描述][a2e0e479d02efe0b316ae0799eb0545b.gif]

我认为是先把组分好，在组内排序，然后扩大长度，最后自然合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 4. 完整代码 ##

**（1）四个函数**

合并函数：void Merge(int input[], int output[], int low, int mid, int high)
    分块函数：void MergePass(int input[], int output[], int length, int size)
    排序函数：void MergeSort(int array1[], int size)
    主函数：  int main()

**（2）全部代码**

#include <stdio.h>
    
    void display(int array[], int size) {
        
        for (int i = 0; i < size; i++) {
        
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    // 第一个是排序前的数组，第二个是每次排序后数组
    void Merge(int input[], int output[], int low, int mid, int high) {
        
        int i = low;                        // 第一块初始下标
        int j = mid + 1;                    // 第二块初始下标
        int k = low;                        // 充当合并块的下标
        while ((i <= mid) && (j <= high)) {
         // 判断遍历两个分块结束
            if (input[i] <= input[j]) {
             // 第一块第 i 个值比第二块第 j 值小
                output[k++] = input[i++];   // 把小的值存入第二个数组，即第一块第 i 个值
            } else {
        
                output[k++] = input[j++]; // 小的值存入第二个数组，即第二块第 j 个值
            }
        }
        while (i <= mid) {
                    // 第一块没遍历完，而第二块遍历结束，说明第一块剩余值都大于第二块
            output[k++] = input[i++]; // 直接把剩余第一块数据都存入第二个数组
        }
        while (j <= high) {
                   // 第二块没遍历完，而第一块遍历结束，说明第二块剩余值都大于第一块
            output[k++] = input[j++]; // 直接把剩余第二块数据都存入第二个数组
        }
    }
    
    // 第一个是排序前的数组，第二个是每次排序后数组
    void MergePass(int input[], int output[], int length, int size) {
        
        int i = 0;                                                       // i 指向第一个分块归并的起始点
        while (i + 2 * length - 1 < size) {
                                      // 分块
            Merge(input, output, i, i + length - 1, i + 2 * length - 1); // 归并分块排序
            i = i + 2 * length;                                          // 归并间隔，指向下一个分块的起始点
        }
    
        /**
         * 1. 不足以分成两个完整块
         *      - 前一个满足 length   (i + length - 1) < size - 1       
         *      - 后一个小于 length   (i + 2 * length - 1) > size - 1   
         * 2. 剩下分块小于等于一个分块
         *      - 将剩余数据复制到 output 中
         */
        if ((i + length - 1) < size - 1) {
        
            Merge(input, output, i, i + length - 1, size - 1);
        } else {
        
            for (int j = i; j < size; j++) {
        
                output[j] = input[j];
            }
        }
    }
    
    void MergeSort(int array1[], int size) {
        
        int array2[size] = {
        0};
        int length       = 1;
        while (length < size) {
        
            MergePass(array1, array2, length, size); // 归并，结果在 array2 中
            length = 2 * length;                     // 改变归并长度，一般是二路归并
            display(array2, size);                   // 打印 array2
            MergePass(array2, array1, length, size); // 归并，结果在 array1 中
            length = 2 * length;                     // 改变归并长度
            display(array1, size);                   // 打印 array1
        }
    }
    
    int main() {
        
        int array[] = {
        49, 38, 65, 97, 76, 13, 27, 49, 10};
        int size    = sizeof(array) / sizeof(int);
    
        // 打印原始数据
        printf("%d \n", size);
        display(array, size);
        MergeSort(array, size);
        return 0;
    }

## 5. 结果展示 ##

（显示每次排序结果）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

## 5. 算法分析 ##

时间复杂度：

1.  最好：O(n log2 n)
2.  最坏：O(n log2 n)
3.  平均：O(n log2 n)

空间复杂度：O(n)

稳定性：稳定

[a2e0e479d02efe0b316ae0799eb0545b.gif]: /images/20220117/b9e1faec46404763b88428c6cc235ab4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20220117/54e12339a6d745a09e2c7e56e43ebe8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20220117/b9c79faa6115403b85f483f95b841ab8.png