「数据结构」八大排序(超详解 附动图 源码)(16)

7.2非递归实现

非递归实现的思想与递归实现的思想是类似的。
不同的是，这里的序列划分过程和递归是相反的，不是一次一分为二，而是先1个元素一组，再2个元素一组，4个元素一组....直到将所有的元素归并完。
静态图示：

代码如下：
// 归并排序非递归实现void MergeSortNonR(int* a, int n){ int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc"); exit(-1); } //初始化每组的元素个数为1 int gap = 1; while (gap < n)//gap为n时就只有一个序列了，所以gap<n { //归并每两组归并一次 int i = 0; for (i = 0; i < n; i =2*gap)//两组中的元素个数为2*gap { //控制两组边界 int begin1 = i, end1 = i gap - 1; int begin2 = i gap, end2 = i 2 * gap - 1; //当原数组中元素个数不是2^n时，最后两组组会出现元素不匹配的情况 //情况1：
end1>=n或begin2>=n,即最后两组中只有一组有元素，则不需归并 if (end1 >= n || begin2 >= n) { break; } //情况2：end2>=n，即最后两组中，第二组元素个数小于第一组，则需要调整第二组边界 if (end2 >= n) { end2 = n - 1; } //归并 int j = i; 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 ]; } //将归并后的有序序列拷贝到原数组中 for (j = i; j <= end2; j ) { a[j] = tmp[j]; } } //每次循环每组元素个数增大2倍 gap *= 2; } free(tmp); tmp = NULL;}