アルゴリズム:統合並べ替え(Merge Sort)
9905 ワード
アルゴリズムの定義
統合順序付けは再帰的アルゴリズムであり、考え方は以下の通りである.ソース配列長が1であれば、すぐに戻ります. はソース配列を二つの新しい配列に分けます.LeftとRight. は、Leftに対して再帰的順序付けを実行する. は、Rightに対して再帰的順序付けを実行する. は、順序付けされたLeftとRightを元の配列にマージする. アルゴリズムを変更するポイントは、配列を並べ替えた統合プロセスであることがわかる.
アルゴリズムの例
【5,4,3,2,1】
【5,4,3】【2,1】
【5,4】【3】【2,1】
【5】【4】【3】【2、1】
【4,5】【3】【2,1】
【3,4,5】【2,1】
【3,4,5】【2】【1】
【3,4,5】【1,2】
【1、2、3、4、5】
アルゴリズム
配列を並べ替えた統合プロセスは、それぞれLeftとRightに対して左から右へのポインタを維持しています.それぞれは、leftIndexとRight Indexであり、ターゲット配列のi番目の要素を充填する場合、LeftとRightから残りの要素(ポインタから最後の部分までの要素)の最小値を見つけなければなりません.とRight[Right Index]の大きさを目標配列のi番目の位置に最小の要素を充填すればいいです.その後、対応するポインタに1を追加します.
統合順序付けは再帰的アルゴリズムであり、考え方は以下の通りである.
アルゴリズムの例
【5,4,3,2,1】
【5,4,3】【2,1】
【5,4】【3】【2,1】
【5】【4】【3】【2、1】
【4,5】【3】【2,1】
【3,4,5】【2,1】
【3,4,5】【2】【1】
【3,4,5】【1,2】
【1、2、3、4、5】
アルゴリズム
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace DataStuctureStudy.Sorts
8 {
9 class MergeSort<T>
10 where T : IComparable<T>
11 {
12 private static void Swap(T[] items, int left, int right)
13 {
14 if (left != right)
15 {
16 var temp = items[left];
17 items[left] = items[right];
18 items[right] = temp;
19 }
20 }
21
22 public static void Sort(T[] items)
23 {
24 if (items.Length < 2)
25 {
26 return;
27 }
28
29 int leftSize = items.Length / 2;
30 int rightSize = items.Length - leftSize;
31
32 T[] left = new T[leftSize];
33 T[] right = new T[rightSize];
34
35 Array.Copy(items, 0, left, 0, leftSize);
36 Array.Copy(items, leftSize, right, 0, rightSize);
37
38 Sort(left);
39 Sort(right);
40 Merge(items, left, right);
41 }
42
43 private static void Merge(T[] items, T[] left, T[] right)
44 {
45 var leftIndex = 0;
46 var rightIndex = 0;
47
48 for (var i = 0; i < items.Length; i++)
49 {
50 if (leftIndex >= left.Length)
51 {
52 items[i] = right[rightIndex];
53 rightIndex++;
54 }
55 else if (rightIndex >= right.Length)
56 {
57 items[i] = left[leftIndex];
58 leftIndex++;
59 }
60 else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)
61 {
62 items[i] = left[leftIndex];
63 leftIndex++;
64 }
65 else
66 {
67 items[i] = right[rightIndex];
68 rightIndex++;
69 }
70 }
71 }
72 }
73 }
統合プロセス配列を並べ替えた統合プロセスは、それぞれLeftとRightに対して左から右へのポインタを維持しています.それぞれは、leftIndexとRight Indexであり、ターゲット配列のi番目の要素を充填する場合、LeftとRightから残りの要素(ポインタから最後の部分までの要素)の最小値を見つけなければなりません.とRight[Right Index]の大きさを目標配列のi番目の位置に最小の要素を充填すればいいです.その後、対応するポインタに1を追加します.