不能在c++中实现归并排序

Question

我是新的算法，我一直试图得到合并排序工作，但它只是不会给出正确的输出。没有编译错误，但我猜它只是有缺陷的地方，在输出中显示随机值作为排序数组。

void merge_sort(int[], int, int);
void merge(int[], int, int, int);
void printarray(int[], int);
int main() {
    int Arr[100], num_of_elements;
    cout << "Enter the number of elements (max 100): ";
    cin >> num_of_elements;
    cout << "Enter array elements: n";
    for (int i = 0;i < num_of_elements;++i)
        cin >> Arr[i];
    merge_sort(Arr, 0, num_of_elements - 1);
    cout << "nAfter Sorting (by Merge Sort):n";
    printarray(Arr, num_of_elements);
    cout << endl;
    return 0;
}
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }  
}
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    /* Calculate the lengths of the subarrays and copy the elements into them */
    int lenght_left = mid - left + 1;
    int length_right = right - mid;
    int *leftarray = new int[lenght_left];
    int *rightarray = new int[length_right];
    for (i = 0;i < lenght_left;++i)
        leftarray[i] = arr[left + i];
    for (j = 0;j < length_right;++j)
        rightarray[j] = arr[mid + 1 + j];
    /* Reordering the elements in the original array */
    for (k = left, i = 0, j = 0;k <= right;++k) {
        if (leftarray[i] <= rightarray[j])
            arr[k] = leftarray[i++];
        else
            arr[k] = rightarray[j++];
    }  
    /* Copy remaining elements into the array */
    while (i < lenght_left)
        arr[k] = leftarray[i++];
    while (j < length_right)
        arr[k] = rightarray[j++];
    delete[](leftarray);
    delete[](rightarray);
}
void printarray(int arr[], int num) {
    cout << "Displaying Elements in array: n";
    for (int i = 0;i < num;i++)
        cout << arr[i] << "  ";
}

Answer 1

在您的merge函数中:

/* Reordering the elements in the original array */
for (k = left, i = 0, j = 0; k <= right; ++k) {
//                           ^^^^^^^^^^^
// It should be i < lenght_left && j < length_right
    if (leftarray[i] <= rightarray[j])
        arr[k] = leftarray[i++];
    else
        arr[k] = rightarray[j++];
}

你用来控制循环的条件是不正确的，条件应该是相对于你的leftarray和rightarray，它应该是，当任何一个数组到达它们的终点时，所以改变你的条件为i < lenght_left && j < length_right。

当复制同一函数中的其余元素时:

/* Copy remaining elements into the array */
while (i < lenght_left)
    arr[k] = leftarray[i++];
//     ^^^
while (j < length_right)
    arr[k] = rightarray[j++];
//     ^^^

这里，你忘了增加k，把它们改成k++。

Answer 2

你犯了几个错误:

1. 当你合并

   时，你需要检查你没有超过数组的长度

   即代替:

   for (k = left, i = 0, j = 0;k <= right;++k)
   

   你应该有:

   for (k = left, i = 0, j = 0;k <= right && i <lenght_left && j<length_right;++k)
   

2. 在添加剩余元素时忘记增加数组计数器。即:

   while (i < lenght_left)
       arr[k] = leftarray[i++];
   while (j < length_right)
       arr[k] = rightarray[j++];
   

   你应该有:

   while (i < lenght_left)
       arr[k++] = leftarray[i++];
   while (j < length_right)
       arr[k++] = rightarray[j++];