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

独自のソート済みリストを作成しようとしているようです。

挿入後に要素をシフトする現在のコードは、配列に挿入するときに実行できる最善の方法です。リストの容量を変更したい場合は、現在の配列のスペースが不足するたびに新しい配列を作成するだけで済みます。

編集：

これは、(リンクされたリストではなく) 配列ベースのリストを使用するコストの 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

挿入ポイントから上へではなく、上から下へループを変更すると、コードははるかに高速になります。この変更により、各位置で 3 つではなく 1 つのコピーを実行するだけで済みます。

于 2013-03-28T19:51:19.477 に答える
0

STL コンテナーとアルゴリズムの使用が許可されていない場合でも、レコードを vector に入れ、独自のクイックソートまたはマージソートをコーディングできます。これは簡単です。クイック ソートは、バブル ソートや選択ソートよりも効率的です。

ご参考までに：

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

于 2013-03-28T19:45:32.160 に答える
0

他の投稿で述べたように、同じ配列内に挿入する方が、配列全体を毎回コピーするよりも高速です。

一方、挿入について説明している方法は、挿入ソートに似ています。1 回の挿入操作のコストは O(n) です。ヒープを使用して配列を管理すると、挿入コストが O(log n) になりますが、配列サイズが小さい場合は遅くなる可能性があります。http://en.wikipedia.org/wiki/Binary_heapを参照してください

于 2013-03-28T20:08:33.750 に答える
0

あなたのケースではSTLデータ構造をチェックアウトする方が良いです.STLを使用できない場合は、ヒープソートまたはクイックソートを試してください.

于 2013-03-28T19:39:19.383 に答える