大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

引言

归并排序（Merge Sort）是一种经典且高效的排序算法，它采用分治法策略来排序数据。下面从原理、递归实现以及非递归实现等多个角度详细介绍归并排序。

那接下来就让我们开始遨游在知识的海洋！

正文

一、归并排序的原理

归并排序的基本思想是将一个待排序的数组分成两个小数组，分别对这两个小数组进行排序，然后将这两个已排序的小数组合并成一个最终的已排序数组。其关键步骤包括分解和合并两个阶段：

• 分解阶段：将待排序的数组分割成两个子数组，直到每个子数组的长度小于或等于1（此时认为是有序的）。
• 合并阶段：将两个有序的子数组合并成一个更大的有序数组，直到最终合并为整个数组的排序结果。

• 归并排序的时间复杂度为O(n log n)，其中n是待排序数组的元素个数。这是因为每次分解都将数组规模减半，而合并操作则需要遍历整个数组。由于分解和合并都是线性时间复杂度的操作，因此总的时间复杂度为O(n log n)。

• 此外，归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序前后保持不变。

二、归并排序的递归实现

• 递归实现是归并排序的一种常见方式。其基本思路是不断地将数组分解成更小的子数组，直到每个子数组只有一个元素或为空，然后再将这些子数组合并起来形成有序的数组。

以下是归并排序递归实现的C语言代码示例：

#include 
#include 

// 合并两个有序数组arr[left...mid]和arr[mid+1...right]到temp[]中
void merge(int arr[], int left, int mid, int right, int temp[]) {
   int i = left;   // 左子数组的起始索引
   int j = mid + 1;// 右子数组的起始索引
   int k = 0;      // 临时数组的索引

   // 将较小的元素放入临时数组中
   while (i <= mid && j <= right) {
       if (arr[i] <= arr[j]) {
           temp[k++] = arr[i++];
       } else {
           temp[k++] = arr[j++];
       }
   }

   // 将剩余的元素放入临时数组中
   while (i <= mid) {
       temp[k++] = arr[i++];
   }
   while (j <= right) {
       temp[k++] = arr[j++];
   }

   // 将临时数组中的元素复制回原数组中
   for (int p = 0; p < k; p++) {
       arr[left + p] = temp[p];
   }
}

// 使用递归对数组arr[left...right]进行归并排序
void mergeSort(int arr[], int left, int right, int temp[]) {
   if (left < right) {
       int mid = left + (right - left) / 2;

       // 对左半部分进行排序
       mergeSort(arr, left, mid, temp);

       // 对右半部分进行排序
       mergeSort(arr, mid + 1, right, temp);

       // 合并左右两部分
       merge(arr, left, mid, right, temp);
   }
}

// 归并排序的主函数
void MergeSortWrapper(int arr[], int n) {
   int *temp = (int *)malloc(n * sizeof(int));
   if (temp == NULL) {
       fprintf(stderr, "Memory allocation failed
");
       exit(EXIT_FAILURE);
   }
   mergeSort(arr, 0, n - 1, temp);
   free(temp);
}

int main() {
   int arr[] = {38, 27, 43, 3, 9, 82, 10};
   int n = sizeof(arr) / sizeof(arr[0]);

   printf("Given array is 
");
   for (int i = 0; i < n; i++) {
       printf("%d ", arr[i]);
   }
   printf("
");

   MergeSortWrapper(arr, n);

   printf("Sorted array is 
");
   for (int i = 0; i < n; i++) {
       printf("%d ", arr[i]);
   }
   printf("
");

   return 0;
}

• 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

• 在这个例子中，merge 函数负责将两个有序的子数组合并成一个有序的数组，而 mergeSort 函数则使用递归来对数组进行分解和排序。最后， MergeSortWrapper 函数为 mergeSort 分配了一个临时数组，并在排序完成后释放了它。

三、归并排序的非递归实现

• 虽然递归实现简洁明了，但在某些情况下可能会导致栈溢出或效率问题。因此，非递归实现也是一种重要的选择。

非递归实现通常采用迭代的方式来进行归并操作。以下是非递归实现的C语言代码示例：

 
#include 
#include 
#include 

// 非递归归并排序函数
void mergeSortNonRecursive(int arr[], int n) {
    int *temp = (int *)malloc(n * sizeof(int));
    if (temp == NULL) {
        fprintf(stderr, "Memory allocation failed
");
        exit(EXIT_FAILURE);
    }

    int gap = 1; // 每次归并操作的子数组大小
    while (gap < n) {
        // 进行一轮归并操作
        for (int i = 0; i < n; i += 2 * gap) {
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;

            // 处理边界情况
            if (end1 >= n) {
                end1 = n - 1;
            }
            if (begin2 >= n) {
                break; // 没有第二个子数组需要归并了
            }
            if (end2 >= n) {
                end2 = n - 1;
            }

            // 合并两个子数组
            int j = begin1;
            int k = 0;
            while (begin1 <= end1 && begin2 <= end2) {
                if (arr[begin1] <= arr[begin2]) {
                    temp[k++] = arr[begin1++];
                } else {
                    temp[k++] = arr[begin2++];
                }
            }
            while (begin1 <= end1) {
                temp[k++] = arr[begin1++];
            }
            while (begin2 <= end2) {
                temp[k++] = arr[begin2++];
            }

            // 将合并后的数组复制回原数组
            memcpy(arr + i, temp + begin1 - i, (end2 - i + 1) * sizeof(int));
        }

        // 增加gap的值以便下一轮归并操作
        gap *= 2;
    }

    free(temp);
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is 
");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");

    mergeSortNonRecursive(arr, n);

    printf("Sorted array is 
");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");

    return 0;
}

• 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

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！