【数据结构与算法】【排序】归并排序的代码实现

客官°小女子只卖身不卖艺 2022-08-13 14:51 190阅读 0赞

归并是指将两个或两个以上的有序表组合成一个新的有序表。

前提：数组元素a\[0\]用作哨兵或临时变量，a\[1\]~a\[n\]存放n个待排序的元素。

基本思想是：假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到\[n/2\]（向上取整）个长度为2或1的有序子序列；再两两归并，...，如此重复，直至得到一个长度为n的有序序列为止。这种排序方法称为2路归并排序。

代码实现（递归和非递归）：

<span style="font-family:SimSun;font-size:18px;">// Filename: merge_sort.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 将两个有序表进行归并，并将最后的结果
    void Merge(int a[], int m, int mid, int n)
    {
        int temp[10];
        int i = m, j = mid + 1, k = 0;
    
        while (i <= mid && j <= n)
        {
            if (a[i] < a[j])
            {
                temp[k++] = a[i++];
            }
            else
            {
                temp[k++] = a[j++];
            }
        }
    
        while (i <= mid) temp[k++] = a[i++];
        while (j <= n) temp[k++] = a[j++];
    
        for (i = m, j = 0; i <= n; i++, j++)
        {
            a[i] = temp[j];
        }
    
        return;
    }
    
    // 归并排序（递归算法）
    // n个元素序列的各元素下标：[1, 2, ..., n-1, n], a[0]作为临时变量
    // 入参m和n分别是待排序元素的起始下标和结尾下标
    void MergeSort1(int a[], int m, int n)
    {
        int mid = (m + n) / 2; // 中间元素的下标
        //int *a1 = &a[m], a1_size = mid - m + 1;
        //int *a2 = &a[mid + 1], a2_size = n - mid;
    
        if (m == n) return;
        MergeSort1(a, m, mid);
        MergeSort1(a, mid + 1, n);
        Merge(a, m, mid, n);
        return;
    }
    
    // 归并排序（非递归算法）
    // n个元素序列的各元素下标：[1, 2, ..., n-1, n], a[0]作为临时变量
    // 入参m和n分别是待排序元素的起始下标和结尾下标
    void MergeSort2(int a[], int m, int n)
    {
        int i;
        int left_min, left_max, right_min, right_max;
    
        for (i = 1; i < n - m + 1; i *= 2)
        {
            left_min = m;
            left_max = m + i - 1;
            right_min = m + i;
            right_max = m + 2 * i - 1;
    
            while (right_min <= n)
            {
                if (right_max > n) right_max = n;
                Merge(a, left_min, left_max, right_max);
                left_min += 2 * i;
                left_max += 2 * i;
                right_min += 2 * i;
                right_max += 2 * i;
            }
        }
    
        return;
    }
    
    // 直接插入排序主函数
    int MergeSortMain()
    {
        int arr[12] = {0xFF, 8, 4, 3, 5, 9, 7, 6, 1, 0, 2, -1};
    
        printf("归并排序演示(a[0]未使用，不参与排序): \n");
    
        printf("排序前：\n");
        printf("arr: ");
        PrintArray(arr, sizeof(arr) / sizeof(int));
        printf("\n");
    
        // 将从a1[1]到a1[10]共10个元素进行排序
        //MergeSort1(arr, 1, 10);
        MergeSort2(arr, 1, 10);
    
        printf("排序后：\n");
        printf("arr: ");
        PrintArray(arr, sizeof(arr) / sizeof(int));
        printf("\n");
    
        return 0;
    }
    </span>