我不太明白为什么要通过自上而下的归并排序来对长度为N的数组进行排序,它只需要6NlogN次数组访问。 (每级需要6N,高度为lgN,所以总共是6NlgN)
每次合并最多使用 6N 次数组访问(2N 次用于复制,2N 次用于移回,最多 2N 次用于比较)
它不是将 N 个元素复制到辅助数组中,然后将其复制回原始数组(即 2N)吗? 2N“后退”是从哪里来的?
这个问题实际上来自算法合并排序中的Progosition G。我想是为了这个。
这是下面书中的代码:
public static void merge(Comparable[] a, int lo, int mid, int hi)
{ // Merge a[lo..mid] with a[mid+1..hi].
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) // Copy a[lo..hi] to aux[lo..hi].
aux[k] = a[k];
for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi].
if (i > mid) a[k] = aux[j++];
else if (j > hi ) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
public class Merge
{
private static Comparable[] aux; // auxiliary array for merges
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length]; // Allocate space just once.
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{ // Sort a[lo..hi].
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid); // Sort left half.
sort(a, mid+1, hi); // Sort right half.
merge(a, lo, mid, hi); // Merge results (code on page 271).
}
}
最佳答案
我所看到的是,您仅将读取操作称为“数组访问”,而本书将读取和写入操作都称为“数组访问”。
查看merge
代码。您在这里有 2 个数组访问:
aux[k] = a[k];
对 a
进行读取操作,对 aux
进行写入操作。然后这里:
a[k] = aux[j++]; //or aux[i++];
您还有另外两个,这次是对 aux
的读取和对 a
的写入。最后,您可能还需要阅读两篇文章:
less(aux[j], aux[i])
总而言之:6 次数组访问(4 次读取和 2 次写入)。
正如您提到的,算法深度为 logN,因此我们得到 6NlogN。
关于arrays - 为什么自顶向下归并排序中数组访问是 6NlogN?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42335993/