クイックソートアルゴリズムの概念
クイックソートは、通常、再帰的な実装に基づいています。アイデアは次のとおりです。
1.適切な値を選択します（理想的な値が最適ですが、アレイの最初の値は一般に「ピボット」と呼ばれます）。
2。この値に基づいて、配列を2つの部分に分割します。左側の小さな部分と右側の大きな部分を分けます。
3.そのようなラウンドの後、このピボットの位置が最終的な位置になければならないことは確かです。
4.アレイごとに1つの要素のみが発生するまで、2つのサブアレイの上記のプロセスを繰り返します。
5.並べ替えが完了しました。
基本的な実装方法：
public static void QuickSort（int [] arr）{qsort（arr、0、arr.length-1）;} private static void qsort（int [] arr、int low、int high）{if（low <high）{int pivot = partition（arr、low、high）; //配列を2つの部分に分割しますqsort（arr、low、pivot-1）。 //左のサブアレイqsort（arr、pivot+1、high）を並べ替えます。 //右のサブアレイを再帰的に並べ替えて}} private static intパーティション（int [] arr、int low、int high）{int pivot = arr [low]; //ピボットレコードwhile（low <high）{while（low <high && arr [high]> = pivot） - high; arr [low] = arr [high]; //左のピボットよりも小さいレコードをスワップします（low <high && arr [low] <= pivot）++ low; arr [high] = arr [low]; //スワップレコードは右端にピボットよりも小さいスワップ} //スキャンが完了し、ピボットが整理されています[low] = pivot; //ピボットの位置を返すことを低く戻します;}ジェネリックを使用して、高速アルゴリズムを実装します
以下は、静的関数sort（）を含むQuickSortクラスです。これには、あらゆるタイプの配列をソートできます。オブジェクトタイプの配列の場合、オブジェクトタイプは比較に比較に使用できるように、比較可能なインターフェイスを実装する必要があります。
最も基本的な高速列ソートアルゴリズムが使用され、最適化処理は実行されませんでした。
ソースコードは次のとおりです。
Import java.util.linkedList; Import java.util.list; import java.util.listiterator; import java.util.random; Public Class QuickSort {@SuppressWarnings（ "Unchecked"）//上記のQuick-row関数プロトタイプを変更して、任意のオブジェクトタイプの配列をソートできるようにします。この関数は内部で使用され、外部ソート関数インターフェイスはsort（）です。ソート関数では、オブジェクトがコンパイルタイムタイプの検出を提供できる同等のインターフェイスを実装する必要があることが必要です。次の記事を参照してください。 private static void quicksort（object [] in、int begin、int end）{if（begin == end || begin ==（end-1））return;オブジェクトp = in [begin]; int a = begin +1; int b = a; for（; b <end; b ++）{//このオブジェクトタイプ配列は、比較可能なインターフェイスを実装する必要があります。これにより、比較機能を使用する必要があります。継続;} object temp = in [a]; in [a] = in [b]; [b] = temp; a ++; }} in [begin] = in [a-1]; [a-1] = p; if（a-1> begin）{quicksort（in、begin、a）; } if（end-1> a）{Quicksort（in、a、end）; } 戻る; } // genericsを使用してオブジェクト配列をソートするには、オブジェクトタイプ配列は比較可能なインターフェイスpublic static <t拡張<？ super t >> void sort（t [] input）{Quicksort（input、0、input.length）; } //並べ替えリストオブジェクトの関数を追加し、java.util.collectionsクラスのsort（）関数を参照して、java public static <t extends carpleable <？ Super t >> void sort（list <t> list）{object [] t = list.toarray（）; //リストを配列QuickSort（t、0、t.length）に変換します。 //配列を並べ替える//配列のソートが完了したら、list Listiterator <t> i = list.listiterator（）に書き戻します。 for（int j = 0; j <t.length; j ++）{i.next（）; i.set（（t）t [j]）; }} //ジェネリックはJava、プリミティブデータ型（int、double、byteなど）で使用できないため、関数過負荷メカニズムを使用してこれらのプリミティブアレイ（int []、double []、byte []など）のみをソートできます。同じソート関数を共有するために、元のタイプ（自動ボクシング、アンボクシング）メカニズムを使用して、対応するオブジェクトタイプにカプセル化し、新しいオブジェクトアレイを形成し、ソートしてからdecapsulateします。これの欠点は、カプセル化された配列を保存するために、追加の変換ステップと追加のスペースが必要であることです。別の方法は、並べ替えコードを各オーバーロードされた関数にコピーすることです。公式APIのjava.util.arraysクラスのsort（）関数は、このメソッドを使用します。これは、アレイクラスのソースコードから見ることができます。 public static void sort（int [] input）{integer [] t = new Integer [input.length]; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; // capsulation} QuickSort（t、0、t.length）; // sorting for（int i = 0; i <input.lengt.lent; i ++）{input [i] = t [i] ;/ suttulation} // deboul sitic of [] boid sitic of boid sitic of [] input）{double [] t = new double [input.length]; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; } QuickSort（t、0、t.length）; for（int i = 0; i <input.length; i ++）{input [i] = t [i]; }} // byteの過負荷関数[]配列public static void sort（byte [] input）{byte [] t = new byte [input.length]; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; } QuickSort（t、0、t.length）; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; } QuickSort（t、0、t.length）; for（int i = 0; i <input.length）; input.length; i ++）{input [i] = t [i]; }} // short []過負荷関数public static void sort（short [] input）{short [] t = new short [input.length]; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; } QuickSort（t、0、t.length）; for（int i = 0; i <input.length; i ++）{input [i] = t [i]; }} // short [] function public static void sort（char [] input）{character [] t = new Character [input.length]; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; } QuickSort（t、0、t.length）; for（int i = 0; i <input.length; i ++）{input [i] = t [i]; }} // floatの過負荷関数[]配列public static void sort（float [] input）{float [] t = new float [input.length]; for（int i = 0; i <input.length; i ++）{t [i] = input [i]; } QuickSort（t、0、t.length）; for（int i = 0; i <input.length; i ++）{input [i] = t [i]; }} // public static void main（string [] args）をテストするためのメイン関数{//乱数で構成されるint []アレイを生成して、int len = 10; int [] input = new int [len];ランダムr = new Random（）; system.out.print（ "sorting："）; for（int i = 0; i <input.length; i ++）{input [i] = r.nextint（10*len）; System.out.print（input [i] + ""）; } system.out.println（）; system.out.print（ "sorting："）;ソート（入力）; for（int i：input）{system.out.print（i + ""）; } system.out.println（）; //文字列[] s = new String [] {"b"、 "、"、 "e"、 "d"、 "f"、 "c"}をテストするために一連の文字列を生成します。 system.out.print（ "sorting："）; for（int i = 0; i <s.length; i ++）{system.out.print（s [i]+""）; } system.out.println（）; system.out.print（ "sorting："）;ソート（s）; for（int i = 0; i <s.length; i ++）{system.out.print（s [i]+""）; } system.out.println（）; // <string> l = new linkedlist <string>（）をテストするために文字列のリストを生成します。 s = new String [] {"b"、 "a"、 "e"、 "d"、 "f"、 "c"}; System.out.print（ "sorting："）; for（int j = 0; j <s.length; j ++）{l.add（s [j]）; System.out.print（s [j] + ""）; } system.out.println（）; sort（l）; System.out.print（ "sorting："）; for（string ts：l）{system.out.print（ts + ""）; } system.out.println（）; }}メイン関数テストを実行し、出力から、クイックソートクラスが正常に機能していることがわかります。
並べ替え前：65 48 92 26 3 8 59 21 16 45INT []ソート後：3 8 16 21 26 45 48 59 65 92String []ソートする前：sorting：baedf linkedlist <文字列>並べ替える前：sorting：baedfc linkedlist <string>並べ替え：abcdef：abcdef