合并排序(C语言实现)

合并排序是一种将待排序序列分成多个子序列，分别进行排序，然后再将排序后的子序列合并成整体有序序列的排序算法。使用递归实现时，该算法的时间复杂度为O(nlogn)，因此被广泛应用。

实现步骤

合并排序可以用以下步骤来实现：

1. 分治：将待排序序列从中间分成两部分，递归地对左右两部分进行排序。
2. 合并：将两个有序子序列合并成一个有序序列。

在实现该算法时需要用到指针，具体的实现步骤如下：

void merge(int arr[], int l, int m, int r) { 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 

    /* 创建临时数组 */
    int L[n1], R[n2]; 

    /* 拷贝数据到临时数组 L 和 R */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 

    /* 按顺序合并临时数组到 arr[l..r] */
    i = 0; // 初始化第一个子数组的下标
    j = 0; // 初始化第二个子数组的下标
    k = l; // 初始化合并后子数组的下标
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) {  // 如果左边的元素小于右边的元素，则将左边的元素放到合并后的数组中
            arr[k] = L[i]; 
            i++; 
        } 
        else {  // 否则，将右边的元素放到合并后的数组中
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 

    /* 拷贝 L[] 的保留元素 */
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 

    /* 拷贝 R[] 的保留元素 */
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 

void mergeSort(int arr[], int l, int r) { 
    if (l < r) { 
        /* 计算中间位置*/
        int m = l+(r-l)/2; 

        // 递归地对左边进行排序
        mergeSort(arr, l, m); 
        // 递归地对右边进行排序
        mergeSort(arr, m+1, r); 

        // 合并排序过后的两个数组
        merge(arr, l, m, r); 
    } 
} 

示例说明

示例一

假设有以下待排序序列：

int arr[] = {12, 11, 13, 5, 6, 7}; 

对该数组进行合并排序，可以依次进行以下步骤：

1. 首先调用 mergeSort(arr, 0, 5)，将数组分成 arr[0..2] 和 arr[3..5] 两部分，递归地对这两部分进行排序。
2. 接着递归调用 mergeSort(arr, 0, 2) 和 mergeSort(arr, 3, 5)，分别对 arr[0..2] 和 arr[3..5] 进行排序。
3. 然后调用 merge(arr, 0, 2, 5)，将排序后的 arr[0..2] 和 arr[3..5] 合并成 arr[0..5]。
4. 最后得到的有序数组为 {5, 6, 7, 11, 12, 13}。

示例二

假设有以下待排序序列：

int arr[] = {7, 2, 6, 3, 9}; 

对该数组进行合并排序，可以依次进行以下步骤：

1. 首先调用 mergeSort(arr, 0, 4)，将数组分成 arr[0..2] 和 arr[3..4] 两部分，递归地对这两部分进行排序。
2. 接着递归调用 mergeSort(arr, 0, 2) 和 mergeSort(arr, 3, 4)，分别对 arr[0..2] 和 arr[3..4] 进行排序。
3. 然后调用 merge(arr, 0, 2, 4)，将排序后的 arr[0..2] 和 arr[3..4] 合并成 arr[0..4]。
4. 最后得到的有序数组为 {2, 3, 6, 7, 9}。