QuickSortは、一般的に使用され、より効率的なソートアルゴリズムであり、インタビュープロセス中によく言及されます。その原則を詳細に説明し、Javaバージョンの実装を提供しましょう。
クイックソートアイデア:
2つの独立した部分は、1回の旅行でデータ要素セットRNをソートすることにより分割されます。キーワードの一部は他の部分よりも小さいです。次に、独立した要素が1つしかなくなるまで、2つの部分のキーワードを1つずつ並べ替え、要素コレクション全体が順調になります。
クイックソートのプロセス - 穴を掘る方法と充填番号(これは非常に鮮やかな名前です)、要素セットr [low ... high]の場合、最初に数字(通常はr [low])を参照として取得します、およびr [low]は、すべての要素をベンチマークとして再配置します。
r [low]よりも小さいそれらはすべて前面に配置され、r [low]よりも大きいものはすべて背面に配置され、r [low]が境界として使用され、r [low ... high]は境界として使用されます。 2つのサブセットに分割されてから分割されます。低い> = highまで。
たとえば、r = {37、40、38、42、461、5、7、9、12}のr = {37、40、38、42、461、5、7、9、12}のクイックソートを実行するプロセスは次のとおりです(注:以下の要素の次の表は0から始まります):
| 元のシーケンス | 37 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 12 |
| 1:高 - >低い | 12 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 12 |
| 1:低 - >高 | 12 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 40 |
| 2:high-> low | 12 | 9 | 38 | 42 | 461 | 5 | 7 | 9 | 40 |
| 2:low-> high | 12 | 9 | 38 | 42 | 461 | 5 | 7 | 38 | 40 |
| 3:高 - >低い | 12 | 9 | 7 | 42 | 461 | 5 | 7 | 38 | 40 |
| 3:low->高 | 12 | 9 | 7 | 42 | 461 | 5 | 42 | 38 | 40 |
| 4:high-> low | 12 | 9 | 7 | 5 | 461 | 5 | 42 | 38 | 40 |
| 4:low->高 | 12 | 9 | 7 | 5 | 461 | 461 | 42 | 38 | 40 |
| 1回限りのソート結果 | 12 | 9 | 7 | 5 | 37 | 461 | 42 | 38 | 40 |
ベースベースの選択を開始= 37、下の表は低= 0、高= 8、high = 8から始まり、r [8] <baseの場合、high位置のコンテンツをr [low]に書き込み、次にhigh位置は空で、低=低+1;
低= 1、r [low]> baseなので、低いものからプローブを開始し、r [low]をr [high]に書き込み、high = high -1;
Low <Highが検出されるため、最初のクイックソートを継続する必要があります。
この時点で、low = 1、high = 7。
低い、低= 2、r [low]>ベースからの検出を開始するため、r [low]はr [high]、high = high-1に書き込まれます。
低いことを検出し続けることは高くなりません
この時点で、低= 2、高= 6、同様に、r [high] <base、r [high]をr [low]に書き込み、低= low+1;
低い、低= 3、高= 6、r [low]>ベース、r [low]を書き込み、r [high]、high = high-1から検出し続けます。
低が高くないことを検出し続けます
この時点で、低= 3、高= 5、同様に、r [high] <base、r [high]をr [low]に書き込み、低= low +1;
r [low]>ベース、r [low]をr [high]に書き込み、high = high -1;
現時点では、Low == High == 4が検出されます。
次に、rsiに1つの要素があるか、要素がないか、rs2 = {461,42,38,40}とrs2 = {461,42,38,40}のサブシーケンスの簡単な並べ替えを行います。
(注:上記の形式では、ソートにいくつかの重複データがあることがわかります(元のデータに複製データはありません)。これは、その場所のデータがクリアされていないためです。メモリのデータを調べます特定の時間にブロックします。次にデータが書かれている場合があります。
クイックソートJava実装:
コードコピーは次のとおりです。
private static boolean isempty(int [] n){
n == null ||を返します。
}
// /////////////////////////////////////////////// ///
/**
*クイックソートアルゴリズムのアイデア - 穴を掘って充填する方法:
*
* @param nアレイはソートされます
*/
public static void QuickSort(int [] n){
if(isempty(n))
戻る;
QuickSort(n、0、n.length -1);
}
public static void Quicksort(int [] n、int l、int h){
if(isempty(n))
戻る;
if(l <h){
int pivot = partition(n、l、h);
QuickSort(n、l、pivot -1);
QuickSort(N、Pivot + 1、H);
}
}
private static intパーティション(int [] n、int start、int end){
int tmp = n [start];
while(start <end){
while(n [end]> = tmp && start <end)
終わり - ;
if(start <end){
n [start ++] = n [end];
}
while(n [start] <tmp && start <end)
Start ++;
if(start <end){
n [end-] = n [start];
}
}
n [start] = tmp;
戻り開始。
}
コードにはこのような関数があります。
コードコピーは次のとおりです。
public static void quicksortswap(int [] n、int l、int h)
この関数は、特定のL位置とH位置の間に設定された要素のデータ要素をソートするように実装できます。
それはすべて迅速な並べ替えのためです。