Ram*_*ein 19
非递归合并排序通过考虑输入数组上的窗口大小1,2,4,8,16..2 ^ n来工作.对于每个窗口(下面的代码中的'k'),所有相邻的窗口对都合并到一个临时空间中,然后放回到数组中.
这是我的单一函数,基于C的非递归合并排序.输入和输出在'a'中.暂时存储在'b'中.有一天,我想要一个就地的版本:
float a[50000000],b[50000000];
void mergesort (long num)
{
int rght, wid, rend;
int i,j,m,t;
for (int k=1; k < num; k *= 2 ) {
for (int left=0; left+k < num; left += k*2 ) {
rght = left + k;
rend = rght + k;
if (rend > num) rend = num;
m = left; i = left; j = rght;
while (i < rght && j < rend) {
if (a[i] <= a[j]) {
b[m] = a[i]; i++;
} else {
b[m] = a[j]; j++;
}
m++;
}
while (i < rght) {
b[m]=a[i];
i++; m++;
}
while (j < rend) {
b[m]=a[j];
j++; m++;
}
for (m=left; m < rend; m++) {
a[m] = b[m];
}
}
}
}
顺便说一句,也很容易证明这是O(n log n).窗口大小的外部循环增长为2的幂,因此k具有log n次迭代.虽然内部循环覆盖了许多窗口,但是给定k的所有窗口都完全覆盖输入数组,因此内部循环为O(n).组合内循环和外循环:O(n)*O(log n)= O(n log n).
Dig*_*oss 15
循环遍历元素,并在必要时通过交换两个来对每个相邻的两个组进行排序.
现在,处理两组的组(任意两组,最可能是相邻组,但你可以使用第一组和最后一组)将它们合并为一组,重复选择每组中最低值的元素,直到所有4个元素合并为一组. 4.现在,除了4个加上可能的余数之外,你什么都没有.使用前一个逻辑的循环,再次执行所有操作,除非此时工作为4个组.此循环运行,直到只有一个组.
从报价Algorithmist:
自下而上合并排序是合并排序的非递归变体,其中数组按一系列过程排序.在每次通过期间,阵列被分成大小为m的块.(最初,m = 1).每两个相邻的块被合并(如在正常的合并排序中),并且下一次传递使用两倍大的m值.
递归和非递归归并排序的时间复杂度都是 O(nlog(n))。这是因为这两种方法都以一种或另一种方式使用堆栈。
在非递归方法中，用户/程序员定义和使用堆栈
在递归方法中，系统内部使用堆栈来存储递归调用的函数的返回地址
您想要使用非递归 MergeSort 的主要原因是为了避免递归堆栈溢出。例如，我正在尝试按字母数字顺序对 1 亿条记录进行排序，每条记录的长度约为 1 KB（= 100 GB）。一个 order(N^2) 排序需要 10^16 次操作，也就是说，即使每次比较操作以 0.1 微秒运行也需要几十年的时间。一个订单 (N log(N)) 合并排序将需要不到 10^10 次操作或不到一个小时才能以相同的操作速度运行。然而，在递归版本的 MergeSort 中，1 亿个元素排序导致对 MergeSort( ) 的 5000 万次递归调用。在每个堆栈递归几百字节时，即使该进程很容易适应堆内存，这也会使递归堆栈溢出。在堆上使用动态分配的内存进行合并排序——我使用了上面 Rama Hoetzlein 提供的代码，但我在堆上使用动态分配的内存而不是使用堆栈——我可以用非递归合并排序，我不会溢出堆栈。网站“堆栈溢出”的适当对话！
PS：感谢您的代码，Rama Hoetzlein。
PPS：堆上有 100 GB？！！嗯，它是 Hadoop 集群上的一个虚拟堆，MergeSort 将在多台共享负载的机器上并行实现......