对非复制数组进行排序-解网

问：

我正在研究我的实验室 #5，它是关于对和等算法进行排序的。除了测量执行时间和其他一些东西之外，我已经完成了一些工作，我遇到了一个问题。Quick SortHeap SortMerge Sort

在此代码中：

  int *arr = fill();
  int size = 10;

  std::cout << "\nMERGE SORT: \n";
  std::cout << "array#1: ";
  print_arr(arr, size);

  merge_sort(arr,size);
  std::cout << "array#2: ";
  print_arr(arr,size);

  std::cout << "\nQUICK SORT: \n";
  std::cout << "array#1: ";
  print_arr(arr, size);

  quick_sort(arr, size);

  std::cout << "array#2: ";
  print_arr(arr, size);

  std::cout << "\nHEAP SORT: \n";
  std::cout << "array#1: ";
  print_arr(arr, size);

  heap_sort(arr, size);

  std::cout << "array#2: ";
  print_arr(arr, size);

  delete[] arr;

我将我的数组传递给所有排序方法，发生的事情是数组得到排序，这工作正常，但随后排序的数组被传递到和 .Merge SortQuick SortHeap Sort

我做了一些研究，我发现我可以用它来创建数组的副本，然后将它们作为副本单独传递，但我知道我的教授不是 STL 的“粉丝”，如果这不是我们最后的手段，通常会告诉我们不要使用它。std::copy()

我对这个 assigment 的限制是一些原型，例如这个函数：

const int MAX = 100000;
int* fill() {
    int* arr = new int[10]; // create a new array of size 100

    // set the seed for the random number generator
    std::srand(static_cast<unsigned int>(std::time(nullptr)));

    for (int i = 0; i < 10; i++) { //!change to MAX
        arr[i] = std::rand() % 10 + 1; // fill the array with random numbers from 1 to 100
    }
    return arr;
}

和

void heap_sort(int *arr, int size);
void merge_sort(int *arr, int size)
void qucik_sort(int *arr, int size)

到目前为止，自从我单独测试它们以来，所有算法都可以工作，但是当我将它们一起运行时，它会对已经排序的数组进行排序。这会影响 QS 算法。

我知道它现在看起来像意大利面条代码，函数指针在 TODO 列表中。

C++ 数组

有几件事与你的代码有关，但不一定与你的问题有关：只在你的程序中调用一次，最好是函数中的第一件事。但也不要使用和，C++有更好的PRNG设施。然后不要自己分配内存。如果您需要真正的动态数组，或者不需要，请使用。srandmainsrandrandstd::vectorstd::array

1赞 Ulrich Eckhardt 5/21/2023

您的教授可能有理由避免使用C++ ISO标准中的STL部分，但对于一般C++来说，这是一个值得怀疑的建议，就像使用矢量新资源和手动资源管理一样。也就是说，关于您的问题，请从您的代码中提取一个最小的可重现示例，并将其包含在您的问题中。作为这里的新用户，也请参加导览并阅读如何提问。

0赞 underloaded_operator 5/21/2023

@Someprogrammerdude我很想，但不幸的是我不能使用 STL 容器

1赞 PaulMcKenzie 5/21/2023

@Dude 如何使用现代C++实现排序算法。

答：

3赞 Chris 5/21/2023 #1

您需要生成数组，然后复制它。您可以执行以下操作：

int* copy_array(int* arr, std::size_t n) {
    int* new_arr = new int[size];

    for (std::size_t i = 0; i < n; i++) {
        new_arr[i] = arr[i];
    }

    return new_arr;
}

然后只需调用它即可在对阵列进行排序之前根据需要创建任意数量的数组副本。

1赞 Lajos Arpad 5/21/2023 #2

您可以像这样手动复制数组：

for (int i = 0; i < size; i++) {
    destination[i] = src[i];
}

或者你可以使用 memcpy。链接中的示例：

/* memcpy example */
#include <stdio.h>
#include <string.h>

struct {
  char name[40];
  int age;
} person, person_copy;

int main ()
{
  char myname[] = "Pierre de Fermat";

  /* using memcpy to copy string: */
  memcpy ( person.name, myname, strlen(myname)+1 );
  person.age = 46;

  /* using memcpy to copy structure: */
  memcpy ( &person_copy, &person, sizeof(person) );

  printf ("person_copy: %s, %d \n", person_copy.name, person_copy.age );

  return 0;
}

而且，当然，您也可以使用，尽管由于教授的喜好，它不是一种选择。std::copy

对非复制数组进行排序

Sorting a non-copy array

评论

评论