摘要：如下归并排序的分析我们先来对两个序列合成新的有序序列进行分析我们以上面的第三趟排序作为例子这就完成了两个序列合并的算法代码如下。
目录
归并是将两个或两个以上的有序表组合成一个新的有序表，假设初始序列含有n个记录，则可看成是n个子序列，每个子序列的长度为1，然后两两归并，得到[ n/2 ]个长度为2或为1的有序的子序列；在两两归并... ... ，如此重复，直到得到一个长度为n的有序序列为止。如下：
我们先来对两个序列合成新的有序序列进行分析;我们以上面的第三趟排序作为例子
这就完成了两个序列合并的算法,代码如下。
void _MergeSortNonR(int* a,int* tmp,int begin1,int end1, int begin2, int end2){ int cur1 = begin1;//cur1是子序列1的指针指向位置 int cur2 = begin2;//cur2是子序列2的指针指向位置 int cur3 = begin1;//临时数组指向的位置 //将子序列1和子序列2进行比较，然后将较小的值 //插入到临时数组中 while (cur1 <= end1 && cur2 <= end2) { if (a[cur1] < a[cur2]) { tmp[cur3] = a[cur1]; cur1++; } else { tmp[cur3] = a[cur2]; cur2++; } cur3++; } //将剩下的子序列的值插入到 //临时数组中 while (cur1 <= end1) { tmp[cur3++] = a[cur1++]; } while (cur2 <= end2) { tmp[cur3++] = a[cur2++]; } //将临时数组中的数组拷贝给原来的数组 for (int i = begin1; i <= end2; i++) { a[i] = tmp[i]; }}其中a是为原数组，tmp是临时数组。begin1和end1为序列1的区间，begin2和end2为序列2的区间。
当然完成两个序列合并只是其中的一部分，要完成归并排序的算法，我们还要继续往下分析：
起初begin1为指向4的位置为0，则endl为begin1+gap-1，begin2为begin1+gap，end2为begin1+2gap-1，其中gap为子序列的间隔，此时的gap为2.
当上面的子序列排完序后，则跳到下一组序列进行排序。则begin1为指向1的位置，其中的begin1由上一个being1+=2gap跳过来的。如果按照上面计算的话，我们在每一趟中的后面需要在判断end2和end1，如果end2大于n-1时，则表示end2比数组最后一个数据的地址要大，所以令end2等于n,如果end1大于n-1时，则表示end1比数组最后一个数据的地址要大，这时候最后一个就只有一个子序列，所以不用在比较了，直接跳出循环循环即可.
当每趟归并排序完成最后一组排序时，则begin1>n,则代表这一趟的归并排序结束，再将gap乘以2倍，进行下一趟的归并排序，当最后一趟排序结束时，其中的gap>=n/2,所以当gap>n时就完成排序.
void MergeSort(int* a, int n){ //创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc申请失败/n"); exit(); } int gap = 1;//第一趟排序的gap为1 while ( gap <= n) { //设i为每两个序列中begin1的值 for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //end2大于n-1，则end2改为n-1 if (n-1 < end2) { end2 =n-1; } //如果end1大于n-1，则这一趟就不需要在排序了 if (n-1 < end1) { break; } //两个序列合成为一个新的序列 _MergeSortNonR(a, tmp, begin1, end1, begin2, end2); } gap *= 2; } //释放临时数组 free(tmp); tmp = NULL;}归并排序的时间复杂度：每一趟归并排序都得遍历一次数组，时间复杂度为O(n),从第一趟都到最后一趟的归并排序总共要进行log2n趟排序，所以归并排序的时间复杂度为O(nlogn).
归并排序的空间复杂度：归并排序需要创建与原来序列一样的临时序列，所以归并排序的空间复杂度为O(N).
内排序：数据数量少，内存中放的下，直接在内存中排序即可,
外排序：数据数量多，内存放不下，数据都放在磁盘中，但不能直接通过内存对它们排序，得在内存中进行一部分排序后，然后在磁盘中完成排序。
外排序的思想：
假设文件A中有5个亿的整数，要对它们进行排序，需要进行怎样排序呢？
（5个亿的整数大约为2个g，内存大概有512个g）
显然这文件A中的数据不能直接放到内存中进行排序，所以就得要使用外排序来对我们的数据进行排序。
好啦，今天的内容就分享到这里了，如果你觉得这篇文章对你有帮助的话，麻烦你给个三连，谢谢!!!
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122140.html
摘要：快速排序在分割的过程中会交换不相邻元素，因此属于不稳定的算法。另一方面，归并排序需要的外部储存空间，快速排序并不需要用到额外内存。也就是说，快速排序是一种原地算法内部排序。快速排序的时间复杂度是，是一般情况下最高效的排序算法。 今天小玄为大家带来平时代码时常用的一种排序方法——快速排序 ...
摘要：两个单元素数组的合并实际就是对这两个数进行了排序，即变为，同样再对后一组的两个数归并排序，即变为，再将两单元数组归并成四单元数组即和归并为。 前言 本周讲解两个50多年前发明，但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序，几乎每个软件系统中都可以找到其中一个或两个的实现，并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...
摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
阅读 3282·2021-10-18 13:30
阅读 1560·2021-10-11 10:58
阅读 2746·2021-10-09 09:44
阅读 1767·2019-08-30 11:26
阅读 2143·2019-08-29 13:17
阅读 648·2019-08-29 12:17
阅读 2136·2019-08-26 18:42
阅读 346·2019-08-26 13:24
