クイック ソートは、効率的なソート アルゴリズムとして広く使用されています。SUN の JDK の Arrays.sort メソッドは、クイック ソートを使用します。
クイック ソートは、古典的な分割統治のアイデアを採用しています。
分割:プリミティブ X (通常は配列の最初の要素) を選択し、分割操作によって配列を 2 つの部分に分割します。左半分は X 以下、右半分は X 以上です。 。
Conquer:左右の部分配列は、Divide プロセスを再帰的に呼び出します。
結合:クイック ソートは、インプレース ソート アルゴリズムとして使用され、マージ操作を必要としません。
クイック ソートの核心部分は分割プロセスであることがわかります。以下は、配列を分割する方法を詳細に説明する例です (画像は「アルゴリズム入門」から引用)。
初期化:配列の最初の要素であるプリミティブ P=2 を選択します。 i=1,j=i+1=2 (配列の添字は 1 から始まります)
ループ不変条件: 2~i の間の要素はすべて P 以下であり、i+1~j の間の要素はすべて P 以上です。
ループ処理: j が 2 から n に進み、位置 j の要素を調べ、それが P 以上の場合、ループを継続します。 P より小さい場合は、位置 j の要素 (範囲 i+1~j に含まれない) を位置 i+1 の要素 (交換後も範囲 i+1~j 内にある) と交換します。これにより、ループの不変条件が維持されます (上記のループの不変条件の説明を参照)。 j=n になるまで、最後のループ操作が完了します。
ループの完了後、最初に設定した要件を満たすために、位置 i の要素を配列の最初の要素と交換する必要があることに注意してください (図の i 番目のステップに対応)。
注意深い読者は、別のより単純な分割方法を考えるかもしれません。つまり、プリミティブを取り出して、それらを同じサイズの別の配列に格納します。プリミティブよりも小さい要素が見つかった場合、それらは配列の左半分に格納されます。要素がプリミティブより大きい場合、要素は配列の左半分に格納されます。要素は配列の右半分に格納されます。このような演算の複雑さも線形、つまり Theta(n) です。ただし、空間の複雑さは 2 倍になります。これは、迅速な仕分けが行われる利点でもあります。
次のようにコードをコピーします。
パブリック クラス クイックソート {
private static void QuickSort(int[] array,int start,int end)
{
if(開始<終了)
{
int key=array[start];//プリミティブを初期化して保存します
int i=start,j;//i,j を初期化する
for(j=start+1;j<=end;j++)
if(array[j]<key)//ここの要素がプリミティブより小さい場合、この要素を i+1 の要素と交換し、プリミティブ以上の場合は i に 1 を加算します。ループ。
{
int temp=配列[j];
配列[j]=配列[i+1];
配列[i+1]=温度;
i++;
}
}
array[start]=array[i];//i で要素とプリミティブを交換します
配列[i]=キー;
QuickSort(array, start, i-1);//再帰呼び出し
QuickSort(配列, i+1, 終了);
}
}
public static void main(String[] args)
{
int[] array=new int[]{11,213,134,44,77,78,23,43};
QuickSort(配列, 0, array.length-1);
for(int i=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}