网站建设方案说明书,app免费制作平台生成,校园网站建设指导思想,网站推广 2015谷歌目录
MergeSortNonR归并排序
非递归归并排序VS快速排序
整体思想
图解分析
代码实现
时间复杂度
归并排序在硬盘上的应用#xff08;外排序#xff09; MergeSortNonR归并排序
前面的快速排序的非递归实现#xff0c;我们借助栈实现。这里我们能否也借助栈去…目录
MergeSortNonR归并排序
非递归归并排序VS快速排序
整体思想
图解分析
代码实现
时间复杂度
归并排序在硬盘上的应用外排序 MergeSortNonR归并排序
前面的快速排序的非递归实现我们借助栈实现。这里我们能否也借助栈去实现归并排序呢
非递归归并排序VS快速排序 快速排序的递归前序递归快速排序的非递归借用栈快速排序的非递归模拟递归借助栈实际上来说快排的非递归模拟回归的过程就是不入栈。实际上是没有这个回归过程的因为快速排序回归不需要处理在分割的时候就已经处理了 归并排序的递归后序递归归并排序的非递归直接分解归并排序回归需要处理然儿借助栈模拟非递归根本没有回归这个过程。 处理根 左 右前序左 右 根处理后序借助栈模拟非递归比较适合前序后序需要复杂处理是不适合的。 整体思想 借助斐波那契数列的非递归思想递归的分治是倒着推非递归的分治是正着推顺着往前推把整个序列直接看成分解之后的不在去分解了。直接合并。一一合并二二合并四四合并等等........(❗万一这个不是2的次方数合并呢❓每小组合并之后拷贝回原数组❗不要在每大组合并完再去拷贝❗因为是一一合并二二合并等等。设置一个gap变量控制每大组的合并 每小组 设置begin1end1begin2end2控制两个区间的序列的合并两段有序序列的合并拷贝 | 每小组合并之后拷贝回原数组❗不要在每大组合并完再去拷贝❗❗区间必须变化起来 每大组 写入循环for完成每gap组的合并拷贝循环使❗区间必须变化起来 整体 gap变化起来结束条件 n 易错点 每小组合并完之后再去拷贝区间合并的起始位置结束位置拷贝的长度问题。合并的组数不一定都是2的次方倍越界问题。可以尝试打印区间来查看越界问题越界问题存在三种情况begin1in不会越界 end1后面两个肯定越界第一序列存在数第二序列不存在数begin2end2肯定越界第二序列不存在数end2可能第二序列区间还存在数 图解分析 代码实现
#includestdio.h
#includestdlib.h
#includestring.h//0 n-1
void MergeSortNonR(int* a, int begin, int end, int* tmp)
{//直接看成分割完合并的int gap 1;//整体while (gap end 1){//每组for (int i 0; i end 1; i 2 * gap){//每小组int begin1 i;//不会越界int end1 i gap - 1;//会越界int begin2 i gap;int end2 i 2 * gap - 1;int j i;//越界结束n if (end1 end 1 || begin2 end 1){break;}//越界修改if (end2 end 1)//注意{end2 end;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else//{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}//begin1变了大哥memcpy(a i, tmp i, sizeof(int) * (end2-i1));}printf(\n);gap gap * 2;}
}int main()
{int a[] { 10,6,7,1,3,9,4,2,9,8,7 };int n sizeof(a) / sizeof(a[0]);int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}MergeSortNonR(a, 0, n - 1, tmp);PrintSort(a, n);free(tmp);return 0;
}
时间复杂度 时间复杂度ON*logN) 归并排序在硬盘上的应用外排序 内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。硬盘归并排序既是内排序也是外排序。 内存和硬盘的区别为什么归并排序可以是外排序其他排序只能是内排序为什么数据要放到硬盘里面大量的数据在文件中保存如果用归并排序使其有序 感谢大家的阅读若有错误和不足欢迎指正。关于归并排序作为外排序在文件中的应用后面的补充内容会详细讲解。
