C# クイックソート

C# クイック ソート

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort
{
    class QuickSorter
    {
        private static int[] myArray;
        private static int arraySize;
        public static int[] Sort(int[] a)
        {
            arraySize = a.Length;
            QuickSort(a, 0,arraySize- 1);
	    return a;
        }
        private static void QuickSort(int[] myArray, int left, int right)
        {
            int i, j, s;
            if (left < right)
            {
                i = left - 1;
                j = right + 1;
                s = myArray[(i + j) / 2];
                while (true)
                {
                    while (myArray[++i] < s) ;
                    while (myArray[--j] > s) ;
                    if (i >= j)
                        break;
                    Swap(ref myArray[i], ref myArray[j]);
                }
                QuickSort(myArray, left, i - 1);
                QuickSort(myArray, j + 1, right);
            }
        }
        private static void Swap(ref int left, ref int right)
        {
            int temp;
            temp = left;
            left = right;
            right = temp;
        }
    }
}

クイック ソートのアイデア:

ソートする配列が A[0]...A[N-1] であると仮定し、最初に任意のデータ (通常は配列の最初の番号) を選択します。 ) をキー データとして、その前にそれより小さいすべての数字を置き、その前にそれより大きいすべての数字を置くこのプロセスは、ワンパス クイック ソートと呼ばれます。クイックソートは安定したソートアルゴリズムではないことに注意してください。つまり、複数の同一の値の相対位置がアルゴリズムの終了時に変わる可能性があります。

ワンパスクイックソートのアルゴリズムは次のとおりです:

1) ソート開始時に 2 つの変数 i と j を設定します: i=0、j=N-1; 2) 最初の配列要素をキーデータとして使用します。 、キーに値を代入します、つまり key=A[0]

3) j から前方検索、つまり後方 (j--) から前方検索し、最初の値 A[j] を見つけます。 key より小さい値の項目を A[j] と交換します

4) i から逆方向に検索、つまり前から逆方向に検索 (i++)、大きい最初の A[i] を見つけます。キー項目を A[i] と交換します

5) ステップ 3 を繰り返します

6) i=j になるまでステップ 3、4、および 5 を繰り返します。条件を満たす値が見つからなかった場合、つまり、3のA[j]がkey以上、4のA[j]がkey以下の場合、jとiの値を次のように変更します。 j=j-1、i=i+1、条件を満たす値が見つかるまで、i==j の処理は常に行われなければなりません。 i+ または j- が完了し、その時点でループが終了します)。

例:

配列を例として、区間内の最初の数値を基数とします。

i = 3; j = 7;

j=5 のとき、条件が満たされていれば a[5] を掘り出して前の穴に埋めます、 a[3] = a[5];

から逆方向に開始します。 i 検索、i=5 の場合、i==j なので終了します。

このとき、i = j = 5で、a[5]がたまたま前回掘った穴なので、a[5]にXを入れます。

配列は次のようになります:

上記は C# クイック ソートの内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) に注目してください。