排序算法之归并排序讲解
今天我们继续来讲排序算法，归并排序，难度一般，但是效率也还不错。
老规矩，先搞清楚原理，再写代码。
归并排序分为两个步骤，先是拆分，然后再合并。
我们先来看下合并。
假设有两个有序的数组，一个是1、3、5，一个是2、4、6、8，把他们合并成一个有序的数组。
这个操作应该极其简单。两个下标，一块新的内存。
1和2比较，1小，把1放在新的内存中，x向后走。
2和3比较，2小，把2放在内存中，y向后走。
下面依次把4和5放进去，最后x达到了末尾，y变成了6的下标，那就把y后面的数据全部放进去就行。
这个过程就是合并。
那么问题又来了，去哪找两个有序的数组。
这个就需要对数组做拆分。
比如数组有8个元素，我们先从中间拆开，得到两个数组，每个4个元素。
但是这两个数组也不是有序的，于是对两个数组继续拆分。
左边是两个数组，每个数组两个元素，右边也一样。
这样还不够，继续拆分，最后得到的数组只有一个元素。
如果一个数组只有一个元素，那么它一定就是有序的。
这个过程就需要用到递归。
过程清楚了，下面就是用代码来实现它。
#include #include #include #define size 100000void merge(int *a, int start, int mid, int end){ int left_len = mid - start + 1; int right_len = end - mid; int *l = (int *)malloc(sizeof(int) * left_len); int *r = (int *)malloc(sizeof(int) * right_len); int i, k = start, j; for (i = 0; i < left_len; i++, k++) { l[i] = a[k]; } for (i = 0; i < right_len; i++, k++) { r[i] = a[k]; } for (i = 0, j = 0, k = start; i < left_len && j r[j]) { a[k] = r[j++]; } else { a[k] = l[i++]; } } if (i < left_len) { for (; i < left_len; i++, k++) { a[k] = l[i]; } } if (j < right_len) { for (; j = end) return; int mid = (end + start) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge(a, start, mid, end);}int main(){ int num, arr[size] = {0}, i; //随机产生数组 srand(time(null)); for (i = 0; i < size; i++) { arr[i] = rand() % 100; } merge_sort(arr, 0, size - 1); for (i = 0; i < size; i++) { printf(%d , arr[i]); } printf(); return 0;}归并排序难度不大，但是和堆排序一样，数据越多，顺序越乱，效率越高。
当然，归并排序的缺点就是，需要更多的内存空间。
实体自由形式制造的PCB设计
CAN总线标准接口与布线规范
CMMB TD-SCDMA手机低成本解决方案面世
华为召开全屋智能及全场景新品春季发布会
韩国金融监管机构将为国内的数字货币交易所引入反洗钱规定
排序算法之归并排序讲解
Linux IPC Pipe
高工年会演讲回顾：超级算力，赋能整车中央计算
索尼新机惊艳设计配合VR而生 5.9寸+2K屏+6G
can总线是单线还是双线 can总线通讯最少需要几根线
柴油发电机的工作原理以及基本结构的介绍
探究太赫兹发展史以及特性与应用
N5242A网络分析仪介绍
用可控硅制作的一种触摸开关,Touch switch
世界首条高温超导高速磁浮样车下线启用
什么是Mailto
亚马逊、小米、联想各路大咖为何都跨界做智能家居？
人工智能时代！未来一二十年，每3个月将消失6%的工作
高空作业车用的电控系统解决方案
复享光学显微角分辨光谱仪完成国家科技部科技成果入库
老规矩，先搞清楚原理，再写代码。
归并排序分为两个步骤，先是拆分，然后再合并。
我们先来看下合并。
假设有两个有序的数组，一个是1、3、5，一个是2、4、6、8，把他们合并成一个有序的数组。
这个操作应该极其简单。两个下标，一块新的内存。
1和2比较，1小，把1放在新的内存中，x向后走。
2和3比较，2小，把2放在内存中，y向后走。
下面依次把4和5放进去，最后x达到了末尾，y变成了6的下标，那就把y后面的数据全部放进去就行。
这个过程就是合并。
那么问题又来了，去哪找两个有序的数组。
这个就需要对数组做拆分。
比如数组有8个元素，我们先从中间拆开，得到两个数组，每个4个元素。
但是这两个数组也不是有序的，于是对两个数组继续拆分。
左边是两个数组，每个数组两个元素，右边也一样。
这样还不够，继续拆分，最后得到的数组只有一个元素。
如果一个数组只有一个元素，那么它一定就是有序的。
这个过程就需要用到递归。
过程清楚了，下面就是用代码来实现它。
#include #include #include #define size 100000void merge(int *a, int start, int mid, int end){ int left_len = mid - start + 1; int right_len = end - mid; int *l = (int *)malloc(sizeof(int) * left_len); int *r = (int *)malloc(sizeof(int) * right_len); int i, k = start, j; for (i = 0; i < left_len; i++, k++) { l[i] = a[k]; } for (i = 0; i < right_len; i++, k++) { r[i] = a[k]; } for (i = 0, j = 0, k = start; i < left_len && j r[j]) { a[k] = r[j++]; } else { a[k] = l[i++]; } } if (i < left_len) { for (; i < left_len; i++, k++) { a[k] = l[i]; } } if (j < right_len) { for (; j = end) return; int mid = (end + start) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge(a, start, mid, end);}int main(){ int num, arr[size] = {0}, i; //随机产生数组 srand(time(null)); for (i = 0; i < size; i++) { arr[i] = rand() % 100; } merge_sort(arr, 0, size - 1); for (i = 0; i < size; i++) { printf(%d , arr[i]); } printf(); return 0;}归并排序难度不大，但是和堆排序一样，数据越多，顺序越乱，效率越高。
当然，归并排序的缺点就是，需要更多的内存空间。
实体自由形式制造的PCB设计
CAN总线标准接口与布线规范
CMMB TD-SCDMA手机低成本解决方案面世
华为召开全屋智能及全场景新品春季发布会
韩国金融监管机构将为国内的数字货币交易所引入反洗钱规定
排序算法之归并排序讲解
Linux IPC Pipe
高工年会演讲回顾：超级算力，赋能整车中央计算
索尼新机惊艳设计配合VR而生 5.9寸+2K屏+6G
can总线是单线还是双线 can总线通讯最少需要几根线
柴油发电机的工作原理以及基本结构的介绍
探究太赫兹发展史以及特性与应用
N5242A网络分析仪介绍
用可控硅制作的一种触摸开关,Touch switch
世界首条高温超导高速磁浮样车下线启用
什么是Mailto
亚马逊、小米、联想各路大咖为何都跨界做智能家居？
人工智能时代！未来一二十年，每3个月将消失6%的工作
高空作业车用的电控系统解决方案
复享光学显微角分辨光谱仪完成国家科技部科技成果入库