Mergesort的执行速度很慢

小编典典

Mergesort的执行速度很慢

algorithm

我正在做一份有关C
++中不同排序算法的报告。让我感到困惑的是，我的语言mergesort似乎比heapsort两种语言都慢。我所看到的是那heapsort应该慢一些。

我mergesort对大小100000为19.8 ms 的未排序数组进行heapsort排序，同时对9.7
ms进行排序。我mergesort在C ++中的函数的代码如下：

void merge(int *array, int low, int mid, int high) {
    int i, j, k;
    int lowLength = mid - low + 1;
    int highLength = high - mid;

    int *lowArray = new int[lowLength];
    int *highArray = new int[highLength];

    for (i = 0; i < lowLength; i++)
        lowArray[i] = array[low + i];
    for (j = 0; j < highLength; j++)
        highArray[j] = array[mid + 1 + j];

    i = 0; 
    j = 0; 
    k = low; 
    while (i < lowLength && j < highLength) {
        if (lowArray[i] <= highArray[j]) {
            array[k] = lowArray[i];
            i++;
        } else {
            array[k] = highArray[j];
            j++;
        }
        k++;
    }

    while (i < lowLength) {
        array[k] = lowArray[i];
        i++;
        k++;
    }

    while (j < highLength) {
        array[k] = highArray[j];
        j++;
        k++;
    }
}

void mergeSort(int *array, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;

        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);

        merge(array, low, mid, high);
    }
}

阅读 323

2020-07-28

共1个答案

小编典典

示例合并排序是在merge（）中进行数据的分配和复制，并且可以通过更有效的合并排序消除两者。可以在helper /
entry函数中对temp数组进行单个分配，并且可以通过使用两个相互递归函数（如下面的示例）或使用布尔值来根据递归级别更改合并方向来避免复制参数。

这是经过合理优化的C ++自上而下合并排序的示例。自底向上合并排序会稍快一些，在具有16个寄存器的系统上，四向底合并排序仍然要快一些，大约快于快速排序。

// prototypes
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee);
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee);
void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee);

void MergeSort(int a[], size_t n)       // entry function
{
    if(n < 2)                           // if size < 2 return
        return;
    int *b = new int[n];
    TopDownSplitMergeAtoA(a, b, 0, n);
    delete[] b;
}

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
    if((ee - ll) == 1)                  // if size == 1 return
        return;
    size_t rr = (ll + ee)>>1;           // midpoint, start of right half
    TopDownSplitMergeAtoB(a, b, ll, rr);
    TopDownSplitMergeAtoB(a, b, rr, ee);
    TopDownMerge(b, a, ll, rr, ee);     // merge b to a
}

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
    if((ee - ll) == 1){                 // if size == 1 copy a to b
        b[ll] = a[ll];
        return;
    }
    size_t rr = (ll + ee)>>1;           // midpoint, start of right half
    TopDownSplitMergeAtoA(a, b, ll, rr);
    TopDownSplitMergeAtoA(a, b, rr, ee);
    TopDownMerge(a, b, ll, rr, ee);     // merge a to b
}

void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                      // b[]       index
    size_t l = ll;                      // a[] left  index
    size_t r = rr;                      // a[] right index
    while(1){                           // 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
        }
    }
}

2020-07-28