58网站 做现浇混凝土,网站开发硬件,163邮箱新用户注册,专业营销网络推广哪家好归并排序#xff08;Merge Sort#xff09;是一种高效的排序算法#xff0c;基于分治#xff08;Divide and Conquer#xff09;策略。它将待排序数组分成两个较小的子数组#xff0c;分别对它们进行排序#xff0c;然后将排好序的子数组合并成一个整体有序的数组。归并…归并排序Merge Sort是一种高效的排序算法基于分治Divide and Conquer策略。它将待排序数组分成两个较小的子数组分别对它们进行排序然后将排好序的子数组合并成一个整体有序的数组。归并排序的时间复杂度为O(n log n)在大多数情况下是最佳选择之一。
归并排序的原理
归并排序的过程可以分为两个主要步骤分解和合并。
分解将原始数组递归地分解为较小的子数组直到每个子数组只有一个元素。合并将两个已排序的子数组合并成一个有序的数组不断重复这个过程直到整个数组排序完成。
归并排序的算法步骤 分解 将待排序数组分为两个大致相等的子数组。递归地对每个子数组进行归并排序直到子数组长度为1。 合并 合并两个已排序的子数组为一个新的有序数组。将两个子数组的元素逐个比较依次放入新数组中直到将两个子数组全部合并。 递归结束条件 当子数组长度为1时递归结束。
归并排序的C语言实现
下面是归并排序的C语言实现示例
#include stdio.h
#include stdlib.h// 归并函数用于将两个已排序的数组合并为一个有序数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 mid - left 1; // 左子数组的大小int n2 right - mid; // 右子数组的大小// 创建临时数组int L[n1], R[n2];// 将数据复制到临时数组 L[] 和 R[] 中for (i 0; i n1; i)L[i] arr[left i];for (j 0; j n2; j)R[j] arr[mid 1 j];// 归并临时数组到 arr[left..right]i 0; // 初始化左子数组的索引j 0; // 初始化右子数组的索引k left; // 初始化归并子数组的索引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 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) {int i;for (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(原始数组:\n);printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);printf(排序后的数组:\n);printArray(arr, arr_size);return 0;
}总结
归并排序是一种效率高且稳定的排序算法适用于大规模数据集的排序需求。通过递归地分解和合并数组归并排序可以在O(n log n)的时间复杂度内完成排序因此在实际应用中被广泛使用。通过本文的介绍和C语言实现示例读者可以更深入地理解归并排序的工作原理和实现方式。
