如何在不使用其他数组拆分初始数组的情况下进行合并排序？

Question

我试图解决一个问题，该问题要求编写合并排序代码但不使用其他数组来对初始数组进行分区。我想代码写的差不多好了，但我面临的问题是我无法弄清楚如何在排序时维护和更新数组。我知道问题出在合并函数中。

如何修复代码？

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void PrintArray(int A[], int n)
{
    for(int i=0; i < n; i++)
        printf("%d ", A[i]);
    printf("\n");
}

void merge(int A[], int left, int mid, int right, int n){
  
int B[n];

int i = left, j = mid+1, k=0;

while(i<=mid && j <= right){

  if(A[i]>=A[j]){
    B[k++] = A[i++];
  }

  else {
    B[k++] = A[j++];
  }

}

while(i<=mid){
  B[k++] = A[i++];
}

while(j<=right){
  B[k++] = A[j++];
}

for(i=0; i<n; i++){
  A[i] = B[i];
}

}

void MergeSort(int A[], int left, int right, int n)
{ 
  if(left<right){
    int mid;
    mid = floor((left+right)/2);
    MergeSort(A,left,mid,n/2);
    MergeSort(A,mid+1,right,n/2);
    merge(A,left,mid,right,n);
  }

  else return;
}

int main()
{
    int n;
    scanf("%d",&n);

    int A[n];

    for(int i=0; i < n; i++) scanf("%d", &A[i]);
        
    MergeSort(A, 0, n-1, n);
    PrintArray(A, n);
    return 0;
}

Answer 1

在 merge 的最终 for 循环中，更改：

A[i] = B[i];

进入：

A[left + i] = B[i];

编辑： 即使在修复之后，排序仍然是错误的。最后一个循环的正确修复是：

for (i = left;  i <= right;  ++i)
    A[i] = B[i - left];

原来的 for (i = 0; i < n; ++i) 不起作用，因为只传递 n / 2 可能会传递一个比需要的值少 1 的值。有了这个新修复，n 根本不需要传递给 merge。所以，n 实际上只需要 public 函数。请参阅下面的更新部分。

旁注：

您根本不需要使用 floor。这对于整数数学来说是多余的[并且可能使结果更少准确]。

您正在按反向顺序排序（例如 3, 2, 1 而不是 1, 2, 3）。要按升序排序，请在 merge 中将：if (A[i] >= A[j]) 更改为 if (A[i] <= A[j])

您没有创建一个初始额外数组，但是您在 merge 的堆栈上有 B，所以，您使用 auxiliary/temp 数组。无论您是在 merge 开始时从 A 复制到 B 还是在 merge 结束时从 B 复制回 A 都是如此=]

所以，您没有真正的“就地”算法。

事实上，对于足够大的数组，堆栈上有 B 会导致堆栈溢出。为 B.

使用堆分配可能会更好

您可以将它放在 global/public 的 mergeSort 的“包装器”函数中（例如 mergeSortPublic）。在开始时做（例如）B = malloc(sizeof(int) * n)，在结束时做 free(B)。您可以创建 B 全局范围或将其作为额外参数传递给您的合并函数

更新：

这是一个完全清理过的版本，其中添加了诊断测试。

由于 merge 中最终循环的变化，它不再需要 n 值。因此，在 mergeSort 中不再需要 mergeSortPub 更改。

我重构了 merge 中的第一个循环，通过不重新获取已经获取的数组值来稍微快一些。优化器可能已经发现了这种加速，但我认为最好明确说明。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void
PrintArray(int A[], int n)
{
    int totlen = 0;

    for (int i = 0; i < n; i++) {
        totlen += printf(" %d", A[i]);
        if (totlen >= 72) {
            printf("\n");
            totlen = 0;
        }
    }

    if (totlen > 0)
        printf("\n");
}

void
merge(int A[], int left, int mid, int right, int *B)
{

    int i = left,
        j = mid + 1,
        k = 0;

    int Ai = A[i];
    int Aj = A[j];

    while (i <= mid && j <= right) {
        if (Ai <= Aj) {
            B[k++] = Ai;
            Ai = A[++i];
        }
        else {
            B[k++] = Aj;
            Aj = A[++j];
        }
    }

    while (i <= mid)
        B[k++] = A[i++];

    while (j <= right)
        B[k++] = A[j++];

    // original code
#if 0
    for (i = 0; i < n; i++)
        A[i] = B[i];
#endif

    // first fix -- still broken
#if 0
    for (i = 0; i < n; i++)
        A[left + i] = B[i];
#endif

    // correct fix
#if 1
    for (i = left;  i <= right;  ++i)
        A[i] = B[i - left];
#endif
}

void
MergeSort(int A[], int left, int right, int *B)
{
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(A, left, mid, B);
        MergeSort(A, mid + 1, right, B);
        merge(A, left, mid, right, B);
    }
}

void
MergeSortPub(int A[], int n)
{
    int *B = malloc(sizeof(*B) * n);

    MergeSort(A,0,n - 1,B);

    free(B);
}

void
dotest(int tstno)
{

    int n = rand() % 1000;

    int *A = malloc(sizeof(*A) * n);

    for (int i = 0;  i < n;  ++i)
        A[i] = n - i;

    MergeSortPub(A,n);

    int old = A[0];
    int bad = 0;
    for (int i = 1;  i < n;  ++i) {
        int cur = A[i];
        if (cur < old) {
            if (! bad)
                printf("dotest: %d -- i=%d old=%d cur=%d\n",tstno,i,old,cur);
            bad = 1;
        }
        old = cur;
    }

    if (bad) {
        PrintArray(A,n);
        exit(1);
    }
}

int
main(void)
{
    int n;

#if 0
    scanf("%d", &n);

    int A[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);

    MergeSortPub(A, n);
    PrintArray(A, n);
#else
    for (int tstno = 1;  tstno <= 1000;  ++tstno)
        dotest(tstno);
#endif

    return 0;
}

Answer 2

合并排序的一些变体不使用除局部变量之外的任何其他 space。这个优化实现比较复杂，比传统的归并排序慢50%左右，而且这些实现大多是为了学术研究。

有一篇 wiki 文章针对一种变体，即插入排序和归并排序的混合体。

https://en.wikipedia.org/wiki/Block_sort

Link 到此 github 存储库中 grailsort.h 中的更优化版本。 void GrailSort(SORT_TYPE *arr,int Len) 函数不使用任何额外的缓冲区。

https://github.com/Mrrl/GrailSort

如何在不使用其他数组拆分初始数组的情况下进行合并排序？

How to do merge sort without using additional arrays for splitting the initial array?

c

arrays

sorting

mergesort