Java はクイック ソート アルゴリズム (Quicktsort) を実装します。

クイック ソート アルゴリズムの概要
クイック ソートとマージ ソートはどちらも、分割統治法を使用してアルゴリズムを設計します。違いは、マージ ソートでは、それぞれソート後に配列を基本的に同じ長さの 2 つのサブ配列に分割することです。操作が実行され、サブ配列を分割するときのクイック ソートがより芸術的になります。 分割後、ベンチマーク要素の左側の要素はベンチマーク要素よりも小さくなりません。この方法では、2 つの部分配列を分離するだけでよく、マージ ソートのような結合操作は必要ありません。参照要素の選択は、アルゴリズムの効率に大きな影響を与えます。最良の場合は、2 つのサブ配列が基本的に同じサイズであることです。簡単にするために、最後の要素を選択します。より高度なアプローチでは、最初に中央値を見つけて、その中央値を最後の要素と交換し、同じ手順を実行します。分割はクイックソートの中核です。クイック ソートの最悪の実行時間は O(n2) ですが、予想される実行時間は O(nlgn) です。

クイックソートアルゴリズム Java 実装
1. 配列を 2 つのサブ配列とベース要素に分割します。最後の要素をベース要素として選択し、インデックス変数はベースよりも小さい最新の要素の位置を記録します。基本要素よりも小さい新しい要素が見つかると、インデックスが 1 ずつ増加します。最初の要素から最後から2番目の要素まで順にベース要素と比較し、ベース要素より小さい場合はインデックスを1つ増やし、位置インデックスと現在位置の要素を入れ替えます。ループが終了すると、index+1 は基本要素のあるべき位置を取得し、index+1 を最後の要素と交換します。
2. 2 つのサブ配列 [start,index] と [index+2,end] をそれぞれソートします
「Insertsort の Java 実装」と同様に、まず配列ツール クラスを実装します。コードは次のとおりです:

public class ArrayUtils {

     public static void printArray(int[] array) {
      System.out.print("{");
      for (int i = 0; i < array.length; i++) {
       System.out.print(array[i]);
       if (i < array.length - 1) {
        System.out.print(", ");
       }
      }
      System.out.println("}");
     }
     public static void exchangeElements(int[] array, int index1, int index2) {
      int temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
     }
    }

クイック ソートの Java 実装とテスト コードは次のとおりです:

public class QuickSort {

  public static void main(String[] args) {
   int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
   System.out.println("Before sort:");
   ArrayUtils.printArray(array);
   quickSort(array);
   System.out.println("After sort:");
   ArrayUtils.printArray(array);
  }
  public static void quickSort(int[] array) {
   subQuickSort(array, 0, array.length - 1);
  }
  private static void subQuickSort(int[] array, int start, int end) {
   if (array == null || (end - start + 1) < 2) {
    return;
   }
   int part = partition(array, start, end);
   if (part == start) {
    subQuickSort(array, part + 1, end);
   } else if (part == end) {
    subQuickSort(array, start, part - 1);
   } else {
    subQuickSort(array, start, part - 1);
    subQuickSort(array, part + 1, end);
   }
  }
  private static int partition(int[] array, int start, int end) {
   int value = array[end];
   int index = start - 1;
   for (int i = start; i < end; i++) {
    if (array[i] < value) {
     index++;
     if (index != i) {
      ArrayUtils.exchangeElements(array, index, i);
     }
    }
   }
   if ((index + 1) != end) {
    ArrayUtils.exchangeElements(array, index + 1, end);
   }
   return index + 1;
  }
 }

クイック ソート アルゴリズム (Quicktsort) の Java 実装に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。