难以合并排序为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 
     } 
    } 
}