归并排序简介【算法 11】

本文主要是介绍归并排序简介【算法 11】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

归并排序简介

归并排序（Merge Sort）是一种有效的、稳定的、基于分治法的排序算法。它的核心思想是将数组分成更小的部分，分别进行排序后再合并。归并排序具有 (O(n \log n)) 的时间复杂度，在处理大规模数据时表现优异。
请添加图片描述

算法原理

归并排序的工作原理基于“分治法”（Divide and Conquer），即：

分解（Divide）：将未排序的数组一分为二，直到每个子数组仅包含一个元素。
合并（Conquer）：将两个有序的子数组合并成一个有序数组。

具体步骤如下：

将数组从中间划分为两个子数组。
对两个子数组分别进行归并排序。
合并两个有序的子数组。

归并过程详解

合并两个有序数组的步骤如下：

创建一个临时数组 temp，用于存储合并后的数组。
使用两个指针分别指向两个子数组的起始位置，比较这两个位置上的元素，将较小的元素放入 temp，指针后移。
重复上述操作，直到某一个子数组遍历完成。
将未遍历完的子数组剩余元素直接放入 temp。

算法实现

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

#include <stdio.h>// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int leftArr[n1], rightArr[n2];// 分别拷贝左右子数组for (int i = 0; i < n1; i++)leftArr[i] = arr[left + i];for (int j = 0; j < n2; j++)rightArr[j] = arr[mid + 1 + j];int i = 0, j = 0, k = left;// 合并两个有序数组while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}// 将剩余元素放入原数组while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[j];j++;k++;}
}// 递归调用归并排序
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 递归调用左半部分和右半部分mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并两个排序后的数组merge(arr, left, mid, right);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr)/sizeof(arr[0]);printf("Given array is \n");printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);printf("\nSorted array is \n");printArray(arr, arr_size);return 0;
}