改善Mergesort.改进3).在输入和临时数组之间少用一份

Question

我目前正在为我的算法类开发一个项目,我有点停滞不前.通过实施特定的更改,我们被分配了对书中合并排序的改进.我通过前两个变化工作得很好,但第三个变化是杀手.

合并排序(我们正在改进的排序)将输入数组的内容复制到临时数组中,然后将临时数组复制回输入数组.因此它递归地对输入数组进行排序,将两个已排序的一半放入临时数组中.然后它将临时数组中的两半合并在一起,将排序后的序列放入输入数组中.

改进之处在于这种双重复制是浪费的,可以不用.他的提示是:我们可以这样做,以便每次调用Merge只能在一个方向上复制,但是对Merge的调用会改变方向.

这可以通过模糊原始阵列和临时阵列之间的线来完成.

我并不是在寻找代码,因为我相信我可以编写代码.我只是不知道我应该做什么.教授已经离开了这一天所以我不能问他,直到下周我再次上课.

以前有人做过这样的事吗？或者可以为我解读并将其用于非专业术语:P

第一个改进,只要它使用插入排序,只要一个数组变得足够小,它将从时间上大大受益.

第二个改进是停止分配两个动态数组(分类的两半),而是分配1个大小为n的数组,这就是使用的数组而不是两个动态数组.这就是我做的最后一次.代码是:

//#include "InsertionSort.h"
#define INSERTION_CUTOFF 250
#include <limits.h>  // needed for INT_MAX (the sentinel)
void merge3(int* inputArray, int p, int q, int r, int* tempArray)
{
  int i,j,k;
  for (i = p; i <= r; i++)
  {
    tempArray[i] = inputArray[i];
  }
  i = p;
  j = q+1;
  k = p;
  while (i <= q && j <= r)
  {
    if (tempArray[i] <= tempArray[j])
    {
      inputArray[k++] = tempArray[i++];
    }
    else
    {
      inputArray[k++] = tempArray[j++];
    }
  }
}//merge3()

void mergeSort3Helper(int* inputArray, int p, int r, int* tempArray)
{
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int q = (p+r-1)/2;
  mergeSort3Helper(inputArray,p,q,tempArray);
  mergeSort3Helper(inputArray,q+1,r,tempArray);
  merge3(inputArray,p,q,r,tempArray);
}//mergeSort3Helper()

void mergeSort3(int* inputArray, int p, int r)
{
  if (r-p < 1)
  {
    return;
  }
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int* tempArray = malloc((r-p)+1*sizeof(int));
  tempArray[r+1] = INT_MAX;
  mergeSort3Helper(inputArray,p,r,tempArray);
//  This version of merge sort should allocate all the extra space
//  needed for merging just once, at the very beginning, instead of
//  within each call to merge3().
}//mergeSort3()    

Answer 1

算法是这样的：
A1: 7 0 2 9 5 1 4 3
A2: (未初始化)

步骤 1：
A1：不变
A2：0 7 2 9 1 5 3 4

步骤2：
A1：0 2 7 9 1 3 4 5
A2：不变

步骤3：
A1：不变
A2：0 1 2 3 4 5 7 9

这涉及到您每次仅复制一种方式并遵循合并排序的步骤。正如你的教授所说，你通过交替哪个是哪个来模糊工作数组和排序数组之间的界限，并且只有在排序后才进行复制。