在何种情况下合并比选择排序更快

Question

根据随机存储器模型进行计算，给出了使用选择排序可以更有效地排序而用合并排序效率较低的元素数非常低(n << 500000)。但是，当我尝试测试时，我发现选择排序在3分11秒内对500000个元素进行了排序，mergesort在6分44秒内完成了排序。我相信这两种算法的实现是正确的。发生什么事了呢？请解释一下。

对不起，我真的很晚才编辑这个。我失去了网络连接。

这是我的合并：

public class MergeSort {

    // temp array
    public static int temp[];

    public static void merge(int a[], int low, int mid, int high)
    {
       temp = new int [a.length];
       for(int i = low; i <= high; i++)
           temp[i] = a[i];

       int i = low;
       int j = mid + 1;
       int k = low;

       while(i <= mid && j <= high)
       {
           if(temp[i] <= temp[j])
           {
               a[k] = temp[i];
               i++;
           }

           else
           {
               a[k] = temp[j];
               j++;
           }

           k++;
       }

       while(i <= mid)
       {
           a[k] = temp[i];
           k++;
           i++;
       }
    }

    public static void sort(int a[], int low, int high)
    {
        if(low < high)
        {
            int middle = (low + high) / 2;

            // sort the left half
            sort(a, low, middle);

            // sort the right half
            sort(a, middle + 1, high);

            // merge parts
            merge(a, low, middle, high);
        }
    }
}

我的选择是：

public static int[] selSort(int a[])
{
    int length = a.length;
    int temp[] = new int [length];

    System.arraycopy(a, 0, temp, 0, length);

    for(int i = 0; i < length - 1; i++)
    {
        int smIndex = i;

        for(int cIndex = i + 1; cIndex < length; ++cIndex)
            if(temp[cIndex] < temp[smIndex])
                smIndex = cIndex;

        int t = temp[smIndex];
        temp[smIndex] = temp[i];
        temp[i] = t;
    }

    return temp;
}

在选择排序中，我复制数组是有原因的。

Answer 1

问题是merge()基于temp[]分配a.length，而它应该只分配temp = new +1-low。在此修复之后，对tempi的引用应该更改为tempi。

使用当前代码，Java必须分配一个50万个元素数组，即使它只合并一个偶数和一个奇数元素(高+1-低== 2)。

一个经过一定程度优化的自顶向下合并排序示例，它只分配一次临时缓冲区，然后使用相互递归的函数来避免复制。在本例中，ee是结束索引== a.length。这将在不到1/10秒的时间内对500万个整数进行排序，在1.5秒内对10万个整数进行排序。

static void MergeSort(int a[]) {
    if (a.length < 2)
        return;
    int []b = new int[a.length];
    MergeSortAtoA(a, b, 0, a.length);
}

static void MergeSortAtoA(int a[], int b[], int ll, int ee)
{
    if (ee - ll > 1) {
        int rr = (ll + ee)>>1;          // midpoint, start of right half
        MergeSortAtoB(a, b, ll, rr);
        MergeSortAtoB(a, b, rr, ee);
        Merge(b, a, ll, rr, ee);        // merge b to a
    }
}

static void MergeSortAtoB(int a[], int b[], int ll, int ee)
{
    if (ee - ll > 1) {
        int rr = (ll + ee)>>1;          //midpoint, start of right half
        MergeSortAtoA(a, b, ll, rr);
        MergeSortAtoA(a, b, rr, ee);
        Merge(a, b, ll, rr, ee);        // merge a to b
    } else if ((ee - ll) == 1) {
        b[ll] = a[ll];
    }
}

static void Merge(int []a, int []b, int ll, int rr, int ee) {
    int o = ll;                         // b[]       index
    int l = ll;                         // a[] left  index
    int r = rr;                         // a[] right index
    while(true){                        // merge data
        if(a[l] <= a[r]){               // if a[l] <= a[r]
            b[o++] = a[l++];            //   copy a[l]
            if(l < rr)                  //   if not end of left run
                continue;               //     continue (back to while)
            while(r < ee){              //   else copy rest of right run
                b[o++] = a[r++];
            }
            break;                      //     and return
        } else {                        // else a[l] > a[r]
            b[o++] = a[r++];            //   copy a[r]
            if(r < ee)                  //   if not end of right run
                continue;               //     continue (back to while)
            while(l < rr){              //   else copy rest of left run
                b[o++] = a[l++];
            }
            break;                      //     and return
        }
    }
}