Java でクイックソートアルゴリズムの QuickSort を実装する方法の図による説明

バブルソートや選択ソートなどのアルゴリズムと比較すると、クイックソートの特定のアルゴリズム原理と実装はやや困難です。クイック ソートをよりよく理解するために、クイック ソートのアルゴリズム原理を例の形式で詳細に説明します。前のソートアルゴリズムでは、5 人のアスリートの身長ソート問題を例として説明しましたが、クイックソートの特性をよりよく反映するために、ここではさらに 3 人のアスリートを追加します。例の 8 人の選手の詳細と身長情報は次のとおりです (F、G、H は新人選手): A(181)、B(169)、C(187)、D(172)、E( 163)、F(191)、G(189)、H(182)

以前の並べ替えアルゴリズムでは、これらの並べ替えはすべてコーチによって完了していましたが、選手の数が増えたので、コーチもまた、休憩する機会があったので、コーチは 2 人のアシスタントを呼び、クイックソート方法を使用して 8 人の選手の身長を左から右、低いものから高いものに分類するように依頼しました。

クイックソート法のアルゴリズム原理に従って、下の図に示すように、2人のアシスタントがアスリートの配置の両側に立ちます

まず、アシスタント1が配置からアスリートを選択します（通常は1番目のアスリート）左のプレイヤーまたは中央のプレイヤー）、ここではプレイヤー A（181）を選択します。ソートは左から右、低位から高位の順であるため、アシスタント 1 は、比較のためのベンチマークとして、身長が A(181) (選択された A(181)) より小さいアスリートを必要とします。選択されたアスリート A (181) の比較):

引き続き、クイック ソートの第 1 ラウンドの詳細な図を参照してみましょう。

並べ替えと検索のプロセス中に 2 人のアシスタントが出会ったとき、彼らは現在のラウンドの比較を停止し、最初に選択されたアスリート A (181) を 2 つの空のラウンドに置きます。アシスタントが出会う席

クイックソートでは、2 人のアシスタントが出会うと、現在のソートラウンドが終了します。このとき、二人の選手が出会う位置A(181)を分割点とすると、配置の左側にある選手は全員A(181)よりも身長が低い選手であり、右側にある選手は全てA(181)よりも身長が低い選手であることが分かる。配置の側は、身長が A(181) アスリートよりも高いすべてのアスリートです。このとき、A(181) の左側と右側の 2 つの並べ替えを個別に見ていきます。上記の 2 つのアシスタントの並べ替え方法を引き続き使用して両側の並べ替えを行うと、複数の並べ替えが行われた後になります。 , ようやく必要な並べ替え結果を取得できます。

上記はクイックソートのソート実装プロセス全体です。クイックソートでは、上記のソートルールを使用して、分割する配列がなくなるまで 1 つの配列を 2 つの配列に、2 つの配列を 4 つの配列に分割し、最終的に必要なソート結果を取得します。

ここで、クイック ソートを使用して上記 8 人のアスリートの身長を並べ替える Java コードをプログラムします。

/**
 * 对指定的数组中索引从start到end之间的元素进行快速排序
 * 
 * @param array 指定的数组
 * @param start 需要快速排序的数组索引起点
 * @param end 需要快速排序的数组索引终点
 */
public static final void quickSort(int[] array, int start, int end) {
  // i相当于助手1的位置，j相当于助手2的位置
  int i = start, j = end;
  int pivot = array[i]; // 取第1个元素为基准元素
  int emptyIndex = i; // 表示空位的位置索引，默认为被取出的基准元素的位置
  // 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
  while (i < j) {
    // 助手2开始从右向左一个个地查找小于基准元素的元素
    while (i < j && pivot <= array[j])
      j--;
    if (i < j) {
      // 如果助手2在遇到助手1之前就找到了对应的元素，就将该元素给助手1的"空位"，j成了空位
      array[emptyIndex] = array[emptyIndex = j];
    }
     
    // 助手1开始从左向右一个个地查找大于基准元素的元素
    while (i < j && array[i] <= pivot)
      i++;
    if (i < j) {
      // 如果助手1在遇到助手2之前就找到了对应的元素，就将该元素给助手2的"空位"，i成了空位
      array[emptyIndex] = array[emptyIndex = i];
    }
  }    
  // 助手1和助手2相遇后会停止循环，将最初取出的基准值给最后的空位
  array[emptyIndex] = pivot;
   
  // =====本轮快速排序完成=====
   
  // 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
  if (i - start > 1) {
    quickSort(array, 0, i - 1);
  }
  // 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
  if (end - j > 1) {
    quickSort(array, j + 1, end);
  }
}
 
//主方法
public static void main(String[] args) {
  // =====使用快速排序法对表示8名运动员身高的数组heights进行从低到高的排序=====
  // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
  int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 };
  // 调用快速排序方法
  quickSort(heights, 0, heights.length - 1);
  // 输出排序后的结果
  for (int height : heights) {
    System.out.println(height);
  }
}

上記の Java コードの出力は次のとおりです:

163
169
172
181
182
187
189
191

注: 地域によって考え方が異なるため、 、上記のクイックソート コードの実装にはさまざまなバリエーションが存在する可能性があります。ただし、どのような形のバリエーションであっても、クイックソートという核となる考え方は変わりません。

別の実装: 一方向スキャン
クイック ソート配列分割には、別の一方向スキャン バージョンがあります。具体的な手順は、配列内の最後の要素を分割要素として選択し、2 つのポインター (ポインター i を指す) を設定することです。は配列内の最初の要素の前の位置であり、j は配列内の最初の要素を指します。 j は前から右、左から右にスキャンし、分割要素以下の要素に遭遇すると i を 1 つ増やし、i と j が指す要素を交換します。最後に、位置 i+1 の要素を分割要素と交換して、配列の分割を完了します。コードは次のように実装されています:

int partition(int[] a, int lo, int hi) {
  int i = lo - 1, j = lo;
  int v = a[hi];
  while (j < hi) {
    if (a[j] <= v) {
      swap(a, ++i, j);
    }
    j++;
  }
  swap(a, i + 1, hi);
  return i + 1;
}

Java で QuickSort アルゴリズムを実装する方法を説明するその他の画像とテキストについては、PHP 中国語 Web サイトの関連記事に注目してください。