1

我需要对数千条记录的数组进行排序。我每次都将新记录放在正确的位置，因此我必须更改数组中其余记录的索引。我手动制作，例如：

    db[j]=record;
    cout<<tmp.oName<<endl;
    while (j++!=size-1){
        tmp2=db[j];
        db[j]=tmp;
        tmp=db[j];
    }

我的问题来了：创建新数组和使用副本会明显更快，还是在我当前的代码旁边没有明显的计算时间和内存使用增强？我对 C++ 很陌生，所以我不确定这个函数在内部是如何工作的。

包括，我可以使用：

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
4

8 回答 8

2

如果您复制数组然后复制到它，它会更慢并使用更多内存。

假设您有一个包含 N 个点的数组，而 I 是您的新项目所在的索引。复制数组意味着您使用 N 更多内存并复制元素 N 次。如果您只是移动记录，则不再使用内存并执行 NI 操作，因为您只需要在新元素之后移动元素。

于 2013-03-28T19:48:15.930 回答
1

不，创建一个新数组不会更快。不过，不使用冒泡排序会更快。而是使用快速排序之类的东西。只需谷歌快速排序 c++ 即可查看它的数百个示例。

于 2013-03-28T19:44:40.267 回答
1

听起来您正在尝试创建自己的排序列表。

您当前的代码（在插入后移动元素）是您在插入数组时可以做的最好的事情。如果您希望更改列表的容量，则只需在当前阵列中的空间不足时创建一个新阵列。

编辑：

这是使用基于数组的列表（与链表相反）的成本之一——插入需要线性时间 O(N)

于 2013-03-28T19:46:58.340 回答
1

如果您在现实生活中需要它，请使用 STL qsort ( http://www.cplusplus.com/reference/cstdlib/qsort/ )。如果你需要它来做家庭作业，那么创建一个新数组的成本会很高，因为运行 malloc 需要时间。

于 2013-03-28T19:47:17.857 回答
0

最好在您的情况下检查 STL 数据结构。如果您不能使用 STL，请尝试堆排序或快速排序。

于 2013-03-28T19:39:19.383 回答
0

如果不允许使用 STL 容器和算法，您仍然可以将记录放入向量中，然后编写自己的快速排序或合并排序，这很简单。快速排序比冒泡排序或选择排序更有效。

供参考：

http://www.algolist.net/Algorithms/Sorting/Quicksort

于 2013-03-28T19:45:32.160 回答
0

如果您将循环更改为从上到下到插入点而不是从插入点到顶部，则代码会快得多。通过这种更改，您只需为每个位置制作一份副本，而不是三份。

于 2013-03-28T19:51:19.477 回答
0

正如在其他帖子中提到的，在同一个数组中插入应该比每次都复制整个数组更快。

另一方面，您描述的插入方式类似于插入排序。一次插入操作将花费您 O(n)。使用堆来管理您的数组将使插入成本 O(log n)，但对于较小的数组大小可能会更慢。见http://en.wikipedia.org/wiki/Binary_heap

于 2013-03-28T20:08:33.750 回答