Mergesort執行速度很慢

Iam在C++中執行關於不同排序算法的報告。讓我感到困惑的是，我的mergesort似乎比兩種語言的heapsort都慢。我所看到的是heapsort應該會變慢。Mergesort執行速度很慢

我的mergesort以19.8毫秒的速度排序一個大小爲100 000的未排序數組，同時heapsort將它排序爲9.7 ms。在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); 
} 
}

來源

2017-01-15 FYOL

您正在分配。別。 – BeyelerStudios

從哪裏知道堆排序比合並排序慢？時間線性的額外拷貝操作在no。子數組的元素在堆中不存在。這使用相當精確的空間，只有最佳的東西，如何COM應該更昂貴？ –

從大o符號看來，heapsort應該會變慢。 – FYOL

示例歸併排序是做在合併數據的分配和複製（），並且都能夠與更有效的合併排序來消除。臨時數組的單個分配可以在輔助函數/入口函數中完成，並且通過使用兩個相互遞歸的函數（如下面的例子）或者使用布爾值來改變合併方向（取決於遞歸的級別）參數。

下面是一個C++自頂向下合併排序的例子，它被合理地優化了。自底向上合併排序的速度會稍微快一點，而在具有16個寄存器的系統上，4路底部合併的排序速度仍然快一些，快於快速排序。

// 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 
     } 
    } 
}

來源

2017-01-16 01:40:01 rcgldr

謝謝！是的，我發現分配數組非常無效。 – FYOL

Mergesort執行速度很慢

回答

相關問題