DotNet共通ソートアルゴリズムの概要
データ構造とアルゴリズムは1つのプログラムにとって極めて重要で、今いくつかのアルゴリズムを紹介して、プロジェクトの中で比較的によく使うアルゴリズムはあります:バブルソート、簡単な選択ソート、直接挿入ソート、ヒルソート、スタックソート、集計ソート、高速ソートなどの7中のアルゴリズム.
次に、選択ソートアルゴリズム、ヒルソートアルゴリズム、高速ソートアルゴリズムについて説明します.
(1).ソートアルゴリズムの選択:n-i次キーワード間の比較により、n-i+1個のレコードからキーワードの最小レコードを選択し、i(1以上i以下n)番目のレコードと交換する.
(2).ヒルソート:まずn未満の整数d 1を最初のインクリメンタルとして取り、ファイルのすべての記録をグループ化する.すべての距離d 1の倍数のレコードは同じグループに配置される.まず、各グループ内で直接挿入ソートを行います.次に、2番目のインクリメントd 2をとる
(3).クイックソートアルゴリズム:ソート対象レコードを1回のソートで独立した2つの部分に分割し、一部のレコードのキーワードが他の部分のレコードのキーワードよりも小さい場合、この2つの部分のレコードをそれぞれソートし続け、シーケンス全体の順序付けの目的を達成することができます.
以上はアルゴリズム定義の簡単な説明であり、次にアルゴリズムの具体的な実現を見てみましょう.
1.ソートアルゴリズムタイプのインタフェース:
2.ソートアルゴリズムファクトリクラス:
3.高速ソートアルゴリズム:
次に、選択ソートアルゴリズム、ヒルソートアルゴリズム、高速ソートアルゴリズムについて説明します.
(1).ソートアルゴリズムの選択:n-i次キーワード間の比較により、n-i+1個のレコードからキーワードの最小レコードを選択し、i(1以上i以下n)番目のレコードと交換する.
(2).ヒルソート:まずn未満の整数d 1を最初のインクリメンタルとして取り、ファイルのすべての記録をグループ化する.すべての距離d 1の倍数のレコードは同じグループに配置される.まず、各グループ内で直接挿入ソートを行います.次に、2番目のインクリメントd 2をとる
(3).クイックソートアルゴリズム:ソート対象レコードを1回のソートで独立した2つの部分に分割し、一部のレコードのキーワードが他の部分のレコードのキーワードよりも小さい場合、この2つの部分のレコードをそれぞれソートし続け、シーケンス全体の順序付けの目的を達成することができます.
以上はアルゴリズム定義の簡単な説明であり、次にアルゴリズムの具体的な実現を見てみましょう.
1.ソートアルゴリズムタイプのインタフェース:
///
///
///
internal interface ISortAlgorithm
{
///
/// 。
///
///
///
///
///
///
/// 。
void Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc);
} 2.ソートアルゴリズムファクトリクラス:
///
///
///
internal static class SortAlgorithmFactory
{
///
/// 。
///
///
///
internal static ISortAlgorithm CreateSortAlgorithmImplementation(SortAlgorithm algorithm)
{
ISortAlgorithm toReturn = null;
switch (algorithm)
{
case SortAlgorithm.SelectionSort:
toReturn = new SelectionSorter();
break;
case SortAlgorithm.ShellSort:
toReturn = new ShellSorter();
break;
case SortAlgorithm.QuickSort:
toReturn = new QuickSorter();
break;
}
return toReturn;
}
} 3.高速ソートアルゴリズム:
///
///
///
internal class QuickSorter : ISortAlgorithm
{
///
/// 。
///
///
/// 。
/// 。
/// 。
/// 。
/// 。
void ISortAlgorithm.Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc)
{
Func valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) (compareFunc(a, b) > 0);
break;
default:
throw new ArgumentOutOfRangeException("direction", "Invalid direction specified, can't craete value comparer func");
}
PerformSort(toSort, startIndex, endIndex, valueComparerTest);
}
///
/// ， 。
///
///
/// 。
/// 。
/// 。
/// 。
private static void PerformSort(IList toSort, int left, int right, Func valueComparerTest)
{
while (true)
{
if (right <= left)
{
return;
}
var pivotIndex = Partition(toSort, left, right, left, valueComparerTest);
PerformSort(toSort, left, pivotIndex - 1, valueComparerTest);
left = pivotIndex + 1;
}
}
///
///
///
///
/// 。
/// 。
///
/// 。
/// 。
///
private static int Partition(IList toSort, int left, int right, int pivotIndex, Func valueComparerTest)
{
var pivotValue = toSort[pivotIndex];
toSort.SwapValues(pivotIndex, right);
var storeIndex = left;
for (var i = left; i
4. ：
///
///
///
internal class ShellSorter : ISortAlgorithm
{
///
/// 。
///
///
///
///
///
///
/// 。
void ISortAlgorithm.Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc)
{
Func valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) > 0);
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) = intervalIndex) && valueComparerTest(toSort[j - intervalIndex], currentValue))
{
toSort[j] = toSort[j - intervalIndex];
j -= intervalIndex;
}
toSort[j] = currentValue;
}
}
}
}
5.ソートアルゴリズムを : ///
///
///
internal class SelectionSorter : ISortAlgorithm
{
///
/// 。
///
///
/// 。
/// 。
/// 。
/// 。
/// 。
void ISortAlgorithm.Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc)
{
Func valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) > 0);
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b)
， ， 。
。 ， 。 ， ， 。
UML ：
， ， case ， ， 。