仅将数组的长度作为参数的递归归并排序

Question

我主要了解接受数组、低位整数和高位整数的递归归并排序函数。但是，我好奇地尝试编写一个只接受数组长度的递归合并排序函数。签名是：void merge_sort(int *array, int n); 这比我想象的要难得多。

我将 post 下面的代码，但我的函数（我认为）只是在每次调用 merge_sort() 时拆分数组的前半部分，基本上没有触及数组的后半部分（我想也是）。

我遇到的另一个问题是，当将所有内容从辅助数组复制回原始数组（使用 for 循环）时，我不确定使用什么作为循环的初始条件。下面是我写的递归合并排序，它接受一个低值和一个高值，然后在它下面是只接受长度的 merge_sort。

// Takes in low and high value
void merge_sort(int *array, int lo, int hi)
{
  int mid = lo + (hi - lo) / 2, i = lo, j = mid + 1, k = 0;

  // Auxiliary to store sorted values.
  int *aux = NULL;

  // Base case.
  if (lo >= hi)
    return;

  // Recursive calls.
  merge_sort(array, lo, mid);
  merge_sort(array, mid + 1, hi);

  // Mergy merge.
  aux = malloc(sizeof(int) * (hi - lo + 1));

  if (aux == NULL)
    return;

  while (i <= mid || j <= hi)
  {
    if (i > mid || j <= hi && array[j] < array[i])
      aux[k++] = array[j++];
    else
      aux[k++] = array[i++];
  }

  // Copy everything from the auxiliary array back into the original array.
  for (i = lo; i <=hi; i++)
    array[i] = aux[i - lo];

  free(aux);
}
// Takes in length of the array.
// This is very wrong, but I quickly tried to rewrite
// how I originally tried to tackle this problem
// when I first attempted it for this post.
void merge_sort(int *array, int n)
{
  // Auxiliary to store sorted values.
  int *aux = NULL;

  // Base case. Single element left in the array.
  if (n/2 < 1)
    return;

  // Recursive calls.
  // First call should take in the first half of the array.
  merge_sort(array, n/2);
  // This call should set the base address of the array 
  // to the midpoint of the array.
  merge_sort(array + n/2, n/2);

  // Mergy merge.
  aux = malloc(sizeof(int) * (n + 1));

  if (aux == NULL)
    return;

  while (i <= n/2 || j <= n)
  {
    if (i > n/2 || j <= n && array[j] < array[i])
      aux[k++] = array[j++];
    else
      aux[k++] = array[i++];
  }

  // Not sure how to write this part of the function correctly. 
  // Low is changing with each call to 
  // merge_sort(array, lo, hi), but in this function there is 
  // no lo variable
  //for (i = *lo*; i <= n; i++)
  //  array[i] = aux[i - lo];

  free(aux);
}

编辑：我的目标是在调用合并排序时尝试消除任何差一错误。

Answer 1

这是我的更改 //@

#include<stdlib.h>
#include<stdio.h>
void printArr(int*arr,int n,char c){
  printf("array of size %d: ",n);
  for (int i = 0; i < n; i++)
  {
    printf("%d ",arr[i]);
  }
  printf("%c",c);
}
void merge_sort(int *array, int n)
{
  // Auxiliary to store sorted values.
  int *aux = NULL;

  // Base case. Single element left in the array.
  if (n/2 < 1)
    return;

  // Recursive calls.
  // First call should take in the first half of the array.
  merge_sort(array, n/2);
  // This call should set the base address of the array 
  // to the midpoint of the array.

  //@ till the end of the array: n - n / 2 (for odd initial size of array)
  merge_sort(array + n/2, n -n/2);

  // Mergy merge.
  //@ n is enough not n+1
  aux = malloc(sizeof(int) * (n));

  if (aux == NULL)
    return;
  
  //@start i from 0, j from n / 2 and k from 0
  int i = 0;
  int j = n/2;
  int k = 0;
  // while (i <= n/2 || j <= n)  
  //@ till k fills the whole array from 0 to n
  while(k<n)
  {
    //@ i condition i>=n/2 not i>n/2 also, j condition j<n not j<=n
    if (i >= n/2 || j < n && array[j] < array[i])
      aux[k++] = array[j++];
    else
      aux[k++] = array[i++];
  }

  //@ now aux has the true values for array, from 0 to n so just loop and copy
  for (i = 0; i < n; i++)
   array[i] = aux[i];

  free(aux);
}
int main(){
  int arr[] = {3,2,6,1,8,9,4,7,5};
  merge_sort(arr,9);
  
  printArr(arr,9,'\n');
  
  return 0;
}

仅将数组的长度作为参数的递归归并排序

Recursive merge sort that just takes length of the array as parameter

c

recursion

mergesort