バブルソートの一種の改善は、初期レコードシーケンスがキーワードによって順序付けられるか、基本的に順序付けられる場合、バブリングソートに退化することです。再帰の原則が使用され、その平均パフォーマンスは、同じ大きさO(n longn)のすべての並べ替え方法の中で最適です。平均時間に関しては、現在、最良の内部並べ替え方法と見なされています。
基本的なアイデアは次のとおりです。並べ替えによってデータを2つの独立した部分に分割し、すべてのデータは他の部分のすべてのデータよりも小さくなり、この方法に従ってデータのこれらの2つの部分をすばやく並べ替えます。 。
3つのポインター:最初のポインターは、ピボットキーポインター(ピボット)と呼ばれ、2番目のポインターと3番目のポインターは、それぞれ左の値と右端の値を指して、それぞれ左のポインターと右のポインターです。左のポインターと右のポインターが両側から中央に近づき、近似プロセスでは、ピボットと常に比較し、ピボットよりも小さい要素を下限に移動し、要素を大きく移動します。ハイエンドにピボットすることは、選択後に変化することはありません。
2つの機能が必要です。
①再帰関数public static void Quicksort(int [] n、int left、int右)
②セグメント関数(1つのクイックソート機能)public static intパーティション(int [] n、int left、int右)
Javaソースコード(正常に実行):
コードコピーは次のとおりです。
パッケージtestsortalgorithm;
パブリッククラスQuickSort {
public static void main(string [] args){
int [] array = {49,38,65,97,76,13,27};
QuickSort(Array、0、Array.Length -1);
for(int i = 0; i <array.length; i ++){
system.out.println(array [i]);
}
}
/*最初に、配列に従ってデータプロトタイプとしてアルゴリズムを書き込み、次にスケーラビリティアルゴリズムを書き込みます。配列{49,38,65,97,76,13,27}
* */
public static void QuickSort(int [] n、int left、int右){
int pivot;
if(左<右){
//ピボットピボットとして、小さな要素が左側にあり、大きな要素が右側にあります
pivot =パーティション(n、左、右);
//注文が完全に正しくなるまで、左右のアレイでクイックソートを再帰的に呼び出す
QuickSort(n、左、ピボット-1);
QuickSort(N、Pivot + 1、右);
}
}
public static intパーティション(int [] n、int left、int右){
int pivotkey = n [左];
//ピボットは選択された後に変わることはなく、最終的には中央にあり、小さな前面と大きな背中があります
while(左<右){
while(左<右&& n [右]> = pivotkey) - 右;
//ピボットよりも小さい要素をローエンドに移動し、正しい位置は空に相当し、ピボットキーよりも大きい数が低い位置を埋めるのを待ちます。
n [左] = n [右];
while(左<右&& n [左] <= pivotkey)++左;
//ピボットよりも大きい要素をこの時点で移動し、左の位置は空に相当し、ピボットキーよりも小さい数を待ちます。
n [右] = n [左];
}
//左==右に、この時点で左のビットが空になります。
n [左] = pivotkey;
左に戻ります。
}
}