難以合併排序爲O（n日誌n）

Question

完全披露，我是一名學生，在合併排序時遇到了問題。目的顯然是有一個O（n log n），但它更多n^2。我認爲問題存在於tempList中，就像您在代碼中看到的那樣，但是在程序描述中，它表示使用static int tempList [LIST_SIZE]來避免降級。

下面是我所擁有的，使用start的運行時大約是16000，這對於合併排序來說顯然是漫長的。

void mergeSort(int randomNum[], int lowIdx, int highIdx) 
    { 
     int midIdx; 

     if (lowIdx < highIdx) 
     { 
      midIdx = (highIdx + lowIdx)/2; 
      mergeSort(randomNum, lowIdx, midIdx); 
      mergeSort(randomNum, midIdx + 1, highIdx); 
      merge(randomNum, lowIdx, midIdx, highIdx); 
     } 
    } 

這裏是排序

void merge(int randomNum[], int lowIdx, int midIdx, int highIdx) 
    { 
     static int tempList[MAX_SORT]; 

     for (int count = 0; count <= highIdx; count++) 
      tempList[count] = randomNum[count]; 

     int leftIdx = lowIdx, 
     rightIdx = midIdx + 1, 
     tempPos = lowIdx; 

     while (leftIdx <= midIdx && (rightIdx <= highIdx)) 
     { 
      if (tempList[leftIdx] <= tempList[rightIdx]) 
      { 
       randomNum[tempPos] = tempList[leftIdx]; 
       leftIdx++; 
      } 
      else 
      { 
       randomNum[tempPos] = tempList[rightIdx]; 
       rightIdx++; 
      } 
     tempPos++; 
     } 

     while (leftIdx <= midIdx) 
     { 
      randomNum[tempPos] = tempList[leftIdx]; 
      tempPos++; 
      leftIdx++; 
     } 

     while (rightIdx <= highIdx) 
     { 
      randomNum[tempPos] = tempList[rightIdx]; 
      tempPos++; 
      rightIdx++; 
     } 
    } 

的第二部分節目的細節，我們與100000張的隨機數的陣列，以及使用各種排序算法排序。其他種類正如預期的那樣工作，但與大O應該是什麼相比，這似乎有很大的差距。

有人可以幫忙嗎？

Answer 1

不知道這是你所有的問題，但是這是一個問題：

您從0複製randomNum到tempList到highIdx，但你永遠只能訪問tempList從lowIdx到highIdx。

這意味着您從0複製到lowIdx的所有項目都是浪費的副本。

解決方案：只複製你需要的東西。

for (int count = lowIdx; count <= highIdx; count++) 

Answer 2

您可能想要考慮自下而上的合併排序。示例模板代碼。 a []是要排序的數組，b []是與[]大小相同的臨時數組。排序的數據可能以[]或b []結尾。這可以修改爲始終以[]中的數據結束，在開始時進行通過次數檢查，並且如果會有偶數次通過，則可以選擇跳過交換。

template <typename T> 
T * BottomUpMergeSort(T a[], T b[], size_t n) 
{ 
    for(size_t s = 1; s < n; s += 2)  // swap in place for 1st pass 
     if(a[s] < a[s-1]) 
      std::swap(a[s], a[s-1]); 
    for(size_t s = 2; s < n; s <<= 1){  // s = run size 
     size_t ee = 0;      // init end index 
     while(ee < n){      // merge pairs of runs 
      size_t ll = ee;     // ll = start of left run 
      size_t rr = ll+s;    // rr = start of right run 
      if(rr >= n){     // if only left run 
       rr = n; 
       BottomUpCopy(a, b, ll, rr); // copy left run 
       break;      // end of pass 
      } 
      ee = rr+s;      // ee = end of right run 
      if(ee > n) 
       ee = n; 
      BottomUpMerge(a, b, ll, rr, ee); 
     } 
     std::swap(a, b);     // swap a and b 
    } 
    return a;        // return sorted array 
} 

template <typename T> 
void BottomUpCopy(T a[], T b[], size_t ll, size_t rr) 
{ 
    while(ll < rr){       // copy left run 
     b[ll] = a[ll]; 
     ll++; 
    } 
} 

template <typename T> 
void BottomUpMerge(T a[], T 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 
     } 
    } 
}