まず、2 つの順序付けされたシーケンスをマージする方法を検討します。これは非常に簡単です。2 つのシーケンスの最初の番号を比較し、小さい方を最初に取得した後、対応するシーケンスの番号を削除します。次に、それらを比較します。一方の列が空の場合は、もう一方の列のデータを 1 つずつ取り出します。
次のようにコードをコピーします。
コードを表示
// 順序付けされた配列 a[] と b[] を c[] にマージします
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i、j、k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
それ以外
c[k++] = b[j++];
}
一方 (i < n)
c[k++] = a[i++];
一方 (j < m)
c[k++] = b[j++];
}
順序付けされたシーケンスをマージする効率は比較的高く、O(n) に達する可能性があることがわかります。
順序付けされたシーケンスをマージする上記の問題を解決した後、マージ ソートを見てみましょう。基本的な考え方は、配列を 2 つのグループ A と B に分割することです。これら 2 つのグループのデータがすべて順序付けされていれば、これら 2 つのセットを簡単にまとめることができます。のデータが並べ替えられます。これら 2 つのグループのデータを順番に保つにはどうすればよいでしょうか?
グループ A とグループ B は 2 つのグループに分けることができます。類推により、分離されたグループにデータが 1 つだけある場合、そのグループは秩序に達したとみなして、隣接する 2 つのグループをマージできます。このように、マージ ソートは、まず配列を再帰的に分解し、次に配列をマージすることで完了します。
次のようにコードをコピーします。
コードを表示
// 2 つの順序付けられたシーケンス a[first...mid] と a[mid...last] をマージします。
void mergearray(int a[], int first, int Mid, int last, int temp[])
{
int i = 最初、j = 中間 + 1;
int m = 中間、n = 最後;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
それ以外
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (最初 < 最後)
{
int mid = (最初 + 最後) / 2;
mergesort(a, first, mid, temp); // 左側がソートされます。
mergesort(a, mid + 1, last, temp); // 右側がソートされます。
mergearray(a, first, mid, last, temp); // 2 つの順序付けされた配列をマージします。
}
}
bool MergeSort(int a[], int n)
{
int *p = 新しい int[n];
if (p == NULL)
false を返します。
マージソート(a, 0, n - 1, p);
削除[] p;
true を返します。
}
マージ ソートの効率は比較的高いです。シーケンスの長さを N と仮定します。シーケンスを 10 進数のシーケンスに分割するには、logN ステップが必要です。各ステップは、順序付けされたシーケンスをマージするプロセスです。時間計算量は O( と記録できます。 N) なので、合計は O(N*logN) になります。マージ ソートは毎回隣接するデータに対して実行されるため、O(N*logN) でのマージ ソートのいくつかのソート方法 (クイック ソート、マージ ソート、ヒル ソート、ヒープ ソート) も比較的効率的です。