二.归并排序非递归版本
1.算法剖析
递归改非递归
1.直接改循环(简单)
2.借助数据结构栈模拟递归过程(复杂一点)
这里我们使用循环的方式来做
大家看一下这张图片
2.代码实现
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); int gap = 1;//每组需要归并的数据个数,控制每组有多少个 while (gap < n) { for (int i = 0; i < n; i += 2 * gap) //每一轮for循环都是归并这两组数据 //[i,i+gap-1] [i+gap,i+2*gap-1] // [begin1,end1] [begin2,end2] //所以说每次for循环之后i都要从第一组的begin1到第二组的begin1, //所以要加2*gap //归并到一起 { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //1.归并过程中右半区间可能就不存在 if (begin2 >= n) { break;//此时根本就不用进行归并了 } //2.归并过程中右半区间算多了,修正一下 if (end2 >= n) { end2 = n - 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //以下两个循环只会进一个 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回去 for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); }
难点剖析:1. for (int i = 0; i < n; i += 2 * gap) 每一轮for循环都是归并这两组数据 [i,i+gap-1] [i+gap,i+2*gap-1] [begin1,end1] [begin2,end2] 所以说每次for循环之后i都要从第一组的begin1到第二组的begin1, 所以要加2*gap 归并到一起 2. for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } 必须写j<=end2,不能写j<= i + 2 * gap - 1,因为 //2.归并过程中右半区间算多了,修正一下 if (end2 >= n) { end2 = n - 1; } 出现这种情况时我们将边界修正了一下,到那时如果写为 j<= i + 2 * gap - 1,那就是写死了,导致越界访问了. 3. 拷贝回去 for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } 要放在上面那个for循环的内部 否则如果放在上面的那个for循环外面, 像这样的话 for (int j = 0; j <n; j++) { a[j] = tmp[j]; } 最外层while循环的里面的话会发生一下这种情况 因为如果放在外面的话,当循环到达4个gap==4且i==0时 | 10 6 7 1 |3 9 4 2|2 我们发现第一轮for循环时左右区间都完整 但是第二轮for循环时不仅右半区间不存在,而且连左半区间都残缺不全 也就是说这个2根本不会拷进tmp临时数组中 tmp临时数组中对应位置存放的是一个随机值 但是我们却在最后进行拷贝,这样就会使得原数组对应位置的这个2被随机值所覆盖,出现错误 4.总之,归并排序的非递归最难的点在于边界的修正和思想 5.因为右半区间的边界需要去时刻准备修正 所以这个归并排序的非递归版本使用栈的话就会很麻烦
3.归并排序的用途
归并排序也叫外排序,还可以对文件中的数据进行排序
只有归并排序才能解决这个问题
假设10G的数据放到硬盘的文件中,要排序,如何排呢?
可能内存不够,假设只有1G的内存可以使用
10G的文件,切分成为10个1G的文件,并且让10个1G的文件有序
依次读文件,每次读1G到内存中形成一个数组,用快排对其进行排序
再写到一个文件中,再继续下一个1G的数据
然后再用归并排序把每个1G的文件逐步归并为一个10G的文件
以上就是归并排序的剖析,希望能对大家有所帮助
