数据库网站建设软件,建立网站需要什么设备,深圳网站设计专家乐云seo品牌,网络定制营销原创不易#xff0c;转载请注明出处。欢迎点赞收藏~ 归并排序是一种常见的排序算法#xff0c;它采用了分治的思想。它将一个待排序的数组递归地分成两个子数组#xff0c;分别对两个子数组进行排序#xff0c;然后将排好序的子数组合并成一个有序数组。
具体的归并排序过… 原创不易转载请注明出处。欢迎点赞收藏~ 归并排序是一种常见的排序算法它采用了分治的思想。它将一个待排序的数组递归地分成两个子数组分别对两个子数组进行排序然后将排好序的子数组合并成一个有序数组。
具体的归并排序过程如下
将待排序的数组不断地二分直到每个子数组只剩下一个元素。对每个子数组进行合并操作即将两个有序的子数组合并成一个有序数组。合并操作是通过比较两个子数组的首元素选取较小的元素放入临时数组中然后移动相应的指针重复此过程直到其中一个子数组为空再将另一个子数组中的剩余部分直接放入临时数组中。重复步骤2直到所有的子数组都被合并成一个有序数组。
归并排序的时间复杂度为 O(nlogn)其中 n 表示待排序数组的长度。这是因为在每一层递归中需要将所有的子数组都进行合并而合并两个长度为 n 的有序数组的时间复杂度为 O(n)。总共需要进行 logn 层的递归因此时间复杂度为 O(nlogn)。
归并排序的空间复杂度为 O(n)主要是由于合并过程中需要使用一个临时数组来存储排序结果。
归并排序是一种稳定的排序算法适用于各种规模的数据集。但由于它需要额外的空间来存储临时数组所以在处理大规模数据时可能会占用较多的内存。 以下是一个基于C语言的归并排序示例
#include stdio.h// 合并两个有序数组
void merge(int arr[], int left[], int leftSize, int right[], int rightSize)
{int i 0, j 0, k 0;// 比较两个子数组的元素将较小的元素放入原始数组arr中while (i leftSize j rightSize){if (left[i] right[j]){arr[k] left[i];}else{arr[k] right[j];}}// 将剩余部分的元素放入arr中while (i leftSize){arr[k] left[i];}while (j rightSize){arr[k] right[j];}
}// 归并排序
void merge_sort(int arr[], int size)
{// 递归终止条件当数组只有一个元素时无需继续划分if (size 1){return;}int mid size / 2;int left[mid];int right[size - mid];// 将数组划分为两个子数组for (int i 0; i mid; i){left[i] arr[i];}for (int i mid; i size; i){right[i - mid] arr[i];}// 对两个子数组分别进行归并排序merge_sort(left, mid);merge_sort(right, size - mid);// 合并两个有序子数组merge(arr, left, mid, right, size - mid);
}int main()
{int arr[] {7, 2, 4, 1, 5, 3};int size sizeof(arr) / sizeof(arr[0]);printf(排序前的数组:\n);for (int i 0; i size; i){printf(%d , arr[i]);}merge_sort(arr, size);printf(\n排序后的数组:\n);for (int i 0; i size; i){printf(%d , arr[i]);}putchar(\n);return 0;
}这段代码实现了归并排序算法。归并排序是一种基于分治思想的排序算法它将待排序的数组分成两个子数组分别进行排序然后合并两个有序的子数组从而得到完整的有序数组。
代码中的merge()函数用于合并两个有序数组。它通过比较两个子数组的元素将较小的元素依次放入原始数组arr中。最后将剩余部分的元素放入原始数组中以确保所有元素都被归并到正确的位置。
merge_sort()函数是归并排序的核心部分。它首先递归地将数组划分为两个子数组然后对这两个子数组分别调用merge_sort()函数进行排序。最后调用merge()函数将两个有序的子数组合并为一个有序数组。
在main()函数中我们声明了一个整型数组arr并初始化了一些元素。然后我们调用merge_sort()函数对数组进行归并排序并打印原始数组和排序后的数组。
最终输出的结果是原始数组和排序后的数组。你可以根据需要修改输入的数组和数组长度来验证归并排序的效果。
运行如上代码你可以看到以下输出
