Seri Algoritma - Penyortiran Bagi dan Taklukkan|Membahas Ulang Penyortiran Cepat|Optimasi Penyortiran Cepat|Algoritma Seleksi Cepat

Seri Algoritma--Penyortiran Bagi dan Taklukkan|Membahas Ulang Penyortiran Cepat|Optimasi Penyortiran Cepat|Algoritma Seleksi Cepat

2024-07-12

Kata Pengantar: Artikel ini memberikan jawaban terperinci atas beberapa keraguan tentang pembelajaran awal algoritma pengurutan cepat, dan menyediakan versi optimal dari algoritma pengurutan cepat dasar.

1. Mari kita bahas lagi tentang penyortiran cepat

Inti dari algoritma quick sort adalah分治思想,Strategi memecah belah dan menaklukkan dibagi menjadi tiga langkah berikut:

Dekomposisi: Menguraikan masalah asli menjadi beberapa sub-masalah serupa yang lebih kecil
Solusi: Jika submasalahnya kecil, selesaikan secara langsung; jika tidak, selesaikan submasalah secara rekursif
Penggabungan: Penyelesaian masalah awal sama dengan penggabungan solusi beberapa submasalah.

Diterapkan pada algoritma pengurutan cepat:

Dekomposisi: Apa yang ingin dicapai oleh algoritma pengurutan cepat adalah mengurutkan seluruh array, tetapi skalanya besar, sehingga perlu menemukan cara untuk mengurangi skala; strategi solusinya adalah dengan "memilih elemen benchmark dan membagi array menjadi dua bagian, dengan elemen di sebelah kiri lebih kecil dari elemen patokan, semua elemen di sebelah kanan lebih besar dari elemen referensi." Dengan mengulangi proses di atas, Anda dapat menyelesaikan pengurutan seluruh array. Setelah menyelesaikan operasi ini pada seluruh array, lakukan proses di atas pada interval kiri dan kanan masing-masing.
Urutkan cepat kedua subarray secara rekursif hingga panjang masing-masing subarray adalah 0 atau 1, dan pada saat itulah array akan diurutkan.
Karena subarray telah diurutkan secara terpisah selama rekursi, tidak diperlukan langkah penggabungan tambahan.

2. Implementasi kode dan penjelasan rinci

Kode kunci untuk penyortiran cepat adalah如何根据基准元素划分数组区间(parttion), ada banyak metode dekomposisi, hanya satu metode yang disediakan di sini.挖坑法
Kode:

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

Jawaban terperinci:
1.Mengapastart>=endApakah ini kondisi akhir dari rekursi?

Dekomposisi sub-masalah secara terus menerus. Ukuran akhir dari sub-masalah adalah 1, yaitu hanya ada satu elemen. Tidak perlu melanjutkan dekomposisi saat ini. Penunjuk awal dan akhir menunjuk ke elemen yang sama waktu.

2. Mengapa yang kanan harus didahulukan daripada yang kiri?

Itu tergantung pada siapa yang pergi duluan基准元素的位置,Pada kode di atas, elemen dasar (kunci) adalah elemen paling kiri jika dipindahkan terlebih dahululeft, left pertama-tama menemukan elemen yang lebih besar dari elemen dasar, lalu mengeksekusiarr[right] = arr[left], karena tidak menabungarr[right], elemen ini akan hilang
Jika Anda ke kanan terlebih dahulu, ke kanan terlebih dahulu akan menemukan elemen yang lebih kecil dari elemen dasar, lalu mengeksekusiarr[left]=arr[right], karena yang kiri saat ini belum bergerak, masih berupa pivot, namun pivot tersebut sudah kita simpan dengan menggunakan kunci.

3.Mengapa arr[right]>=key?>Apakah tidak mungkin?

Lebih besar dari atau sama dengan terutama untuk pemrosesan重复元素问题
Misalnya, ada sebuah array[6,6,6,6,6]Jika >, penunjuk kanan tidak akan bergerak, dan penunjuk kiri juga tidak akan bergerak, dan akan terjebak dalam loop tak terbatas.

4. Mengapa disebut metode penggalian lubang?

Ketika penunjuk r bertemu dengan penunjuk pertamaarr[r] = arr[l], saat ini posisi l kosong sehingga membentuk lubang.

3. Optimalisasi penyortiran cepat

Ada dua arah pengoptimalan utama:

Pemilihan pivot nilai benchmark dapat dibuktikan bahwa ketika nilai benchmark dipilih secara acak, kompleksitas waktu quick sort semakin dekatO(N*logN), yaitu kompleksitas waktu terbaik
Pemrosesan elemen berulang: Jika ada sejumlah besar elemen berulang dalam suatu interval, versi algoritma pengurutan cepat di atas akan mengulangi elemen yang sama beberapa kali untuk mengurangi operasi yang berlebihan, gunakan数组分三块Pada saat yang sama, jika Anda menemukan kasus pengujian khusus (array berurutan atau array terbalik), kompleksitas waktu akan menurun menjadiO(N^2)

Pertama, berdasarkan pertanyaan (urutkan berdasarkan warna) memahami apa itu数组分三块
menganalisa

Masukkan deskripsi gambar di sini
Kode:

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

Melihatl,r的起始位置, elemen pertama dan elemen terakhir menjadi miliknya未处理状态, jadi `l, r tidak bisa menunjuk ke dua elemen ini dan harus berada di luar interval
Yang disebut array dibagi menjadi tiga bagian, artinya menggunakan三个指针去分别维护四个区间, salah satu intervalnya adalah未处理区间, saat penunjuk arus terus bergerak, semua interval diproses, dan akhirnya hanya ada tiga interval.

Terapkan ide-ide di atas pada快速排序的parttion中, hasil akhir dibagi menjadi tiga interval
Masukkan deskripsi gambar di sini
Kode:

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

Masukkan deskripsi gambar di sini
2. Pilih nilai dasar secara acak
Pilih secara acak nilai dasar menggunakan angka acak

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

1
2
3

Selesaikan kode yang ditingkatkan:

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

Masukkan deskripsi gambar di sini

Efisiensi meningkat secara signifikan

4. Algoritma pemilihan cepat

Algoritma pemilihan cepat adalah基于快速排序优化版本Kompleksitas waktuO(N)Algoritma pemilihan, skenario penggunaannya adalah第K大/前K大masalah pilihan seperti

01.Elemen terbesar ke-K dalam array
Tautan: https://leetcode.cn/problems/kth-largest-element-in-an-array/
menganalisa

Solusi brute force adalah dengan menggunakannya secara langsungsortUrutkan lalu kembalikan ke yang terbesar ke-K
kompleksitas waktu:O(N*logN)
Kompleksitas ruang:O(logN)Panggilan tumpukan dihasilkan oleh rekursi

Selanjutnya, algoritma seleksi cepat digunakan untuk mengimplementasikanO(N)Kompleksitas waktu
Kode:

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

Ide dari algoritma quick seleksi sangat mirip dengan quick sort. Perbedaannya adalah algoritma quick seleksi hanya mengulang sebagian interval dari setiap hasil partisi, bukan mengulang seluruh interval seperti quick sort, sehingga kompleksitas waktu dari algoritma pemilihan cepat berkurangO(N)

Berbagi teknologi