技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

はじめに: この記事では、クイック ソート アルゴリズムの初期学習に関するいくつかの疑問に対する詳細な回答を提供し、基本的なクイック ソート アルゴリズムの最適化されたバージョンを提供します。

1. クイックソートについてもう一度話しましょう

クイックソートアルゴリズムの中核は次のとおりです。分治思想分割統治戦略は次の 3 つのステップに分かれています。

1. 分解: 元の問題をいくつかの類似した小さなサブ問題に分解します。
2. 解決策: 部分問題が小さい場合は直接解決し、そうでない場合は部分問題を再帰的に解決します。
3. マージ: 元の問題の解は、いくつかのサブ問題の解をマージしたものと同じです。

クイックソートアルゴリズムに適用される:

1. 分解: クイック ソート アルゴリズムが達成したいのは配列全体をソートすることですが、規模が大きいため、その規模を縮小する方法を見つける必要があります。これは、「ベンチマーク要素を選択して配列を分割する」というものです。 2 つの部分で、左側の要素はベンチマーク要素より小さく、右側のすべての要素は基準要素より大きくなります。上記のプロセスを繰り返すことで、配列全体の並べ替えを完了できます。この操作を完了した後、配列全体に対して、左と右の区間でそれぞれ上記の処理を実行します。
2. 各部分配列の長さが 0 または 1 になるまで、2 つの部分配列を再帰的にクイックソートし、その時点で配列がソートされます。
3. サブ配列は再帰中に個別にソートされているため、追加のマージ手順は必要ありません。

2. コードの実装と詳細な説明

クイックソートのキーコードは次のとおりです。如何根据基准元素划分数组区间(parttion), 分解には多くの方法がありますが、ここでは 1 つの方法のみを説明します。挖坑法
コード：

class Solution {
    public int[] sortArray(int[] nums) {
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick(int[] arr, int start, int end) {
        if(start >= end) return;// 递归结束条件
        int pivot = parttion(arr, start, end);
		
		// 递归解决子问题
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

	
	// 挖坑法进行分解
    private int parttion(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) ++left;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

詳細な回答:
1.なぜstart>=end再帰の終了条件でしょうか？

サブ問題を継続的に分解します。サブ問題の最終的なサイズは 1 です。つまり、要素は 1 つだけです。現時点では、開始ポインターと終了ポインターが同じ要素を指すようにする必要はありません。時間。

2. なぜ左ではなく右を先にする必要があるのですか?

誰が最初に行くかによって決まります基准元素的位置,上記のコードでは、最初に移動した場合、ベース要素 (キー) が一番左の要素になります。left、 left は最初にベース要素より大きい要素に遭遇し、その後実行しますarr[right] = arr[left]保存していないためarr[right]、この要素は失われます
最初に右に移動すると、右は最初にベース要素よりも小さい要素に遭遇し、その後実行されます。arr[left]=arr[right]、この時点では左側が移動していないため、まだピボットですが、ピボットはキーを使用して保存されています。

3.なぜ arr[right]>=key なのでしょうか?>それは不可能ですか?

以上は主に処理用です重复元素问题
たとえば、配列があります[6,6,6,6,6]>の場合は右ポインタも動かず、左ポインタも動かず無限ループにはまってしまいます。

4.なぜ穴掘り法と呼ばれるのですか？

r ポインタが最初のポインタに遭遇したとき、arr[r] = arr[l], この時、lの位置は空いており、ピットが形成されています。

---

3. クイックソートの最適化

最適化には主に 2 つの方向があります。

1. ベンチマーク値ピボットの選択は、ベンチマーク値がランダムに選択されると、クイック ソートの時間計算量が近づくことを証明できます。O(N*logN)、つまり最高の時間計算量
2. 繰り返される要素の処理: 間隔内に多数の繰り返し要素がある場合、上記のバージョンのクイック ソート アルゴリズムは、冗長な操作を減らすために同じ要素を複数回繰り返します。数组分三块同時に、特殊なテスト ケース (順次配列または逆配列) に遭遇した場合、時間計算量は次のように低下​​します。O(N^2)

まず、質問に基づいて（色ごとに並べ替える) 理解する数组分三块
分析する

コード：

class Solution {
    public void sortColors(int[] nums) {
        // 分治 --
        // 1.定义三指针
        int i = 0;// 遍历整个数组
        int l = -1, r = nums.length;

        while(i < r) {
            if(nums[i] == 0) swap(nums,++l,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--r,i);
        }
        return;
    }

    private void swap(int[] nums,int x,int y) {
        int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 知らせl,r的起始位置、最初の要素と最後の要素は以下に属します。未处理状态したがって、 `l、r はこれら 2 つの要素を指すことができず、区間の外側になければなりません。
• いわゆる配列は 3 つの部分に分割されます。つまり、三个指针去分别维护四个区间、間隔の 1 つは未处理区间、cur ポインタが移動し続けると、すべての間隔が処理され、最終的には 3 つの間隔だけになります。

上記のアイデアを適用すると、快速排序的parttion中、最終結果は 3 つの区間に分割されます

コード：

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i];  nums[i] = nums[j]; nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2. 基本値をランダムに選択します
乱数を使用して基本値をランダムに選択します

        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        //               起始位置      随机产生的偏移量

1
2
3

改良されたコードを完成させます:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• 効率が大幅に向上

4. クイック選択アルゴリズム

クイック選択アルゴリズムは次のとおりです。基于快速排序优化版本時間複雑さO(N)選択アルゴリズム、使用シナリオは次のとおりです。第K大/前K大などの選択問題

01.配列内の K 番目に大きい要素
リンク: https://leetcode.cn/problems/kth-largest-element-in-an-array/
分析する

• ブルートフォースソリューションはそれを直接使用することですsort並べ替えてから K 番目に大きいものに戻す
• 時間計算量:O(N*logN)
• 空間の複雑さ:O(logN)再帰によって生成されたスタック呼び出し

次に、クイック選択アルゴリズムを使用して実装します。O(N)時間計算量は、
コード：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int start, int end, int k) {
        if(start >= end) return nums[start];
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
		
		// 数组分三块  <pivot  ==pivot  >pivot
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            if(nums[i] < pivot) swap(nums, ++l, i++);
            else if(nums[i] == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r - 1]  [r, end]
        int c = end - r + 1, b = r - 1 - (l + 1) + 1, a = l - start + 1;
        // 分情况讨论  进行选择
        if(c >= k) return qsort(nums, r, end, k);
        else if(b + c >= k) return pivot;
        else return qsort(nums, start, l, k - b - c);// 找较小区间的第(k-b-c)大
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• クイック選択アルゴリズムの考え方はクイック ソートの考え方と非常に似ていますが、違いは、クイック選択アルゴリズムは、クイック ソートのように間隔全体を再帰するのではなく、各パーティション結果の間隔の一部のみを再帰することです。クイック選択アルゴリズムの到着時間の複雑さが軽減されます。O(N)