クイック ソートは、パーティション交換ソート (パーティション交換ソート) とも呼ばれ、クイック ソート、ソート アルゴリズムと呼ばれます。
(推奨チュートリアル: java 学習 Web サイト)
平均的な状況では、n 個の項目を並べ替えるには O(nlog n) (大きな O 表記) の比較が必要です。最悪の場合、O(n^2) 個の比較が必要になりますが、この状況は一般的ではありません。実際、クイックソート O(nlog n) は、ほとんどのアーキテクチャで内部ループを効率的に実現できるため、通常、他のアルゴリズムよりも大幅に高速です。
クイック ソートでは、分割統治戦略を使用してシーケンス (リスト) を 2 つのサブシーケンス (小さい方と大きい方) に分割し、その 2 つのサブシーケンスを再帰的に並べ替えます。
手順は次のとおりです:
ピボット値を選択します。シーケンスから「ピボット」と呼ばれる要素を選択します。
分割: シーケンスを並べ替えます。ベースライン値より小さいすべての要素はベースラインの前に配置され、ベースライン値より大きいすべての要素はベースラインの後ろに配置されます (数値はベースラインの後ろに配置されます)。ベースライン値はどちらの側でも構いません)。この分割が完了すると、基準値の並べ替えが完了する。
サブシーケンスを再帰的に並べ替える: ベースライン値より小さい要素を持つサブシーケンスと、ベースライン値より大きい要素を持つサブシーケンスを再帰的に並べ替えます。
最下位再帰の判定条件は、配列のサイズが0か1であることですが、このとき配列は当然整っています。
(ビデオチュートリアルの推奨: java 学習)
ベンチマーク値を選択するにはいくつかの具体的な方法があります。この選択方法は、ソートの時間パフォーマンスに決定的な影響を与えます。 。
コード実装:
public class QuickSort {
public static void main(String[] args) {
int[] arr = SortUtil.randomArr(6);
SortUtil.printArr(arr);
// sort(arr,0,arr.length-1);
sort1(arr,0,arr.length-1);
// int[] arr1= netherlands(arr,0,arr.length-1);
// SortUtil.printArr(arr1);
SortUtil.printArr(arr);
}
/**
* 快排1.0，时间复杂度O（n²），找出以arr[right]为界的中间位置，小于等于的放左边，大于等于的放右边
* 分为左右2个区域，每个区域重复上面的步骤，直到最后left=right
* @param arr
* @param left
* @param right
*/
public static void sort(int[] arr,int left,int right){
if(left>=right){return;}
int mid = partition(arr,left,right);
sort(arr,left,mid-1);
sort(arr,mid+1,right);
}
/**
* 快排2.0 以arr[right]作为中间值，最差情况时间复杂度O（n²），平均时间复杂度为 O(n logn)
* @param arr
* @param left
* @param right
*/
public static void sort1(int[] arr,int left,int right){
if(left>=right){return;}
int[] mid = netherlands(arr,left,right);
sort1(arr,left,mid[0]-1);
sort1(arr,mid[1]+1,right);
}
private static int partition(int[] arr, int left, int right) {
if (left > right) {
return -1;
}
if (left == right) {
return left;
}
int lessEqual = left - 1;
int index = left;
while (index < right) {
// 情况1,当前位置小于等于标记值，当前位置不动，标记右移
if (arr[index] <= arr[right]) {
lessEqual++;
// 扩大小于等于区域
SortUtil.swap(arr, index, lessEqual);
}
index++;
}
// 右边界位置和大于区域的起始位置交换
SortUtil.swap(arr, ++lessEqual, right);
return lessEqual;
}
/**
* 荷兰国旗问题
* @param arr
* @param left
* @param right
* @return
*/
private static int[] netherlands(int[] arr,int left,int right){
if(left>right){
return new int[]{-1,-1};
}
if(left==right){
return new int[]{left,right};
}
int lessEqual = left-1;
int i = left;
int more = right;
while (i<more){
// 1.i位置==arr[right],i++
if (arr[i]==arr[right]){
i ++;
}
// 2.i位置<arr[right],i位置与小于区域右一个位置交换
else if (arr[i]<arr[right]){
SortUtil.swap(arr,++lessEqual,i++);
}
// 3.i位置>arr[right],i位置与大于区域左一个位置交换，i不动
else if(arr[i]>arr[right]){
SortUtil.swap(arr,i,--more);
}
}
SortUtil.swap(arr,right,more);
return new int[]{lessEqual+1,more};
}
}以上がJavaでクイックソートを実装する（コード例）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。