クイックソートの原理
クイックソートはバブルソートを改良したもので、小さい値を一つずつ比較するのがバブルソートです。 value はソートの目的を達成するためにもう一方の端に置かれます。
クイックソートは、最初に臨界値を選択し、臨界値より小さい値を一方の端に配置し、臨界値より大きい値を配置します。反対側では。前項の方法を繰り返し、臨界値を超えた辺を2回分割して… データを並べ替えたら、クイックソート全体が完了します。
クイック ソート アルゴリズム
コア アルゴリズム:
//QuickSort while(i < j) { while(num[j] > tmp && j > i) --j; while(num[i] <= tmp && i < j) { ++i; } if(i < j) { t = num[i]; num[i] = num[j]; num[j] = t; } } num[left] = num[i]; num[i] = tmp;
以下は完全な QuickSort プログラムです:
//QuickSort.java public class QuickSort { public static void main(String[] args) { int[] num = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; System.out.print("Qriginal array is:"); for (int i = 0; i < num.length; i++) { System.out.print(num[i] + " "); } System.out.println(); //QuickSort quicksort(num, 0, 9); System.out.print("Sorted array is:"); for (int i = 0; i < num.length; i++) { System.out.print(num[i] + " "); } System.out.println(); } public static void quicksort(int[] num, int left, int right) { if(left > right) return; int tmp, i, j, t; tmp = num[left]; i = left; j = right; while(i < j) { while(num[j] > tmp && j > i) --j; while(num[i] <= tmp && i < j) { ++i; } if(i < j) { t = num[i]; num[i] = num[j]; num[j] = t; } } num[left] = num[i]; num[i] = tmp; quicksort(num, left, i - 1); quicksort(num, i + 1, right); } }
プログラムの出力を次の図に示します。
Qriginal array is:10 9 8 7 6 5 4 3 2 1 Sorted array is:1 2 3 4 5 6 7 8 9 10
クイック ソートは他のソート方法より効率的であるため、現時点ではクイック ソートが最適な一般的なソート方法です。 QuickSort の時間計算量は O(nlogn) です。
以上がJava でのクイックソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。