使用多个动态数组进行合并排序

Question

我一直在尝试创建兼容两个动态数组的merge/mergesort函数。我一直在获取输出的内存位置，而不是排序的数字。我尝试了多次使用休息，仍然无法弄清楚发生了什么问题。

template <class T> 
void mergeSort(T list[], int lowerBound, int upperBound) 
{ 
    if (lowerBound < upperBound) 
    { 
     int mid = (lowerBound + upperBound)/2; 
     cout << upperBound << lowerBound << endl; 
     mergeSort(list, lowerBound, mid); 
     cout << upperBound << lowerBound << endl; 
     mergeSort(list, mid + 1, upperBound); 
     merge(list, lowerBound, mid, upperBound); 
    } 
} 

template <class T> 
void merge(T list[], int lowerBound, int mid, int upperBound) 
{ 
    int size1 = mid - lowerBound + 1; 
    int size2 = upperBound - mid; 

    T *tmp1 = new T[size1 + 1]; 
    T *tmp2 = new T[size2 + 1]; 

    for (int i = 0; i < size1; i++) 
    { 
     tmp1[i] = list[lowerBound + i - 1]; 
     cout << "Here" << endl; 
    } 

    for (int i = 0; i < size1; i++) 
    { 
     tmp1[i] = list[lowerBound + i - 1]; 
     cout << tmp1[i] << endl; 
    } 
    system("pause"); 
    for (int j = 0; j < size2; j++) 
    { 
     tmp2[j] = list[mid + j]; 
    } 

    tmp1[size1 + 1] = std::numeric_limits<int>::max(); 
    tmp1[size2 + 1] = std::numeric_limits<int>::max(); 

    int i = 1; 
    int j = i; 

    for (int k = lowerBound; k < upperBound; k++) 
    { 
     if (tmp1[i] <= tmp2[j]) 
     { 
      list[k] = tmp1[i]; 
      i++; 
     } 
     else 
     { 
      list[k] = tmp2[j]; 
      j++; 
     } 
    } 
} 


int main() 
{ 
    double myArray[7] = { 7, 6.4, 6.3, 8, 1, 2, 3 }; 
    for (int i = 0; i < 7; i++) 
    { 
     cout << myArray[i] << " "; 
    } 
    cout << endl; 
    mergeSort(myArray, 0, 7); 
    for (int i = 0; i < 7; i++) 
    { 
     cout << myArray[i] << " "; 
    } 
    return 0; 
} 

Answer 1

合并例程有一些问题。一个问题是size1代表从lowerBound到mid，包括mid的所有指数。这就是中低音+ 1计算的结果。还有一些其他的错误是我在评论中标记的。

当我在想这个实现，我用一个小例子：

int lowerBound = 35, int mid = 37, int upperBound = 40 

我建议通过与这些值码走，看看数学是有道理的。

template <class T> 
void merge(T list[], int lowerBound, int mid, int upperBound) 
{ 
    int size1 = mid - lowerBound + 1; // According to this, mid is 
             // part of the size1 array 
    int size2 = upperBound - mid; 
    T *tmp1 = new T[size1 + 1]; 
    T *tmp2 = new T[size2 + 1]; 

    for (int i = 0; i < size1; i++) 
    { 
     tmp1[i] = list[lowerBound + i - 1]; // Remove - 1 
     cout << "Here" << endl; 
    } 

    for (int i = 0; i < size1; i++) // This for loop is repeated, remove it 
    { 
     tmp1[i] = list[lowerBound + i - 1]; 
     cout << tmp1[i] << endl; 
    } 
    system("pause"); 
    for (int j = 0; j < size2; j++) 
    { 
     tmp2[j] = list[mid + j]; // Mid is not part of the size2 array 
    }       // Use mid + 1 + j (start at mid+1) 

    tmp1[size1 + 1] = std::numeric_limits<int>::max(); // should be tmp1[size1] 
    tmp1[size2 + 1] = std::numeric_limits<int>::max(); // should be tmp2[size2]; Also I couldn't tell if these are part of your debug statements, but I think you mean "tmp2" 

    int i = 1; // This should start at 0 
    int j = i; // This should start at 0 

    for (int k = lowerBound; k < upperBound; k++) // Should be <=; upper 
    {            // Bound is part of the 
     if (tmp1[i] <= tmp2[j])     // merge 
     { 
      list[k] = tmp1[i]; 
      i++; 
     } 
     else 
     { 
      list[k] = tmp2[j]; 
      j++; 
     } 
    } 
}