Κοινή χρήση τεχνολογίας

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

Πρόλογος: Αυτό το άρθρο παρέχει λεπτομερείς απαντήσεις σε ορισμένες αμφιβολίες σχετικά με την πρώιμη εκμάθηση του αλγορίθμου γρήγορης ταξινόμησης και παρέχει μια βελτιστοποιημένη έκδοση του βασικού αλγορίθμου γρήγορης ταξινόμησης.

1. Ας μιλήσουμε ξανά για τη γρήγορη ταξινόμηση

Ο πυρήνας του αλγορίθμου γρήγορης ταξινόμησης είναι分治思想Η στρατηγική διαίρει και βασίλευε χωρίζεται στα ακόλουθα τρία βήματα:

1. Αποσύνθεση: Αναλύστε το αρχικό πρόβλημα σε πολλά παρόμοια, μικρότερα υποπροβλήματα
2. Λύση: Εάν το υποπρόβλημα είναι μικρό, λύστε το απευθείας, διαφορετικά, λύστε το υποπρόβλημα αναδρομικά
3. Συγχώνευση: Η λύση του αρχικού προβλήματος ισούται με τη συγχώνευση των λύσεων πολλών υποπροβλημάτων.

Εφαρμόζεται στον αλγόριθμο γρήγορης ταξινόμησης:

1. Αποσύνθεση: Αυτό που θέλει να πετύχει ο αλγόριθμος γρήγορης ταξινόμησης είναι να ταξινομήσει ολόκληρο τον πίνακα, αλλά η κλίμακα είναι μεγάλη, επομένως πρέπει να βρει έναν τρόπο να μειώσει την κλίμακα η στρατηγική του είναι να "επιλέξει ένα στοιχείο αναφοράς και να χωρίσει τον πίνακα δύο μέρη, με στοιχεία στα αριστερά που είναι μικρότερα από το στοιχείο αναφοράς , όλα τα στοιχεία στα δεξιά είναι μεγαλύτερα από τα στοιχεία αναφοράς." Επαναλαμβάνοντας την παραπάνω διαδικασία, μπορείτε να ολοκληρώσετε την ταξινόμηση ολόκληρου του πίνακα. Αφού ολοκληρώσετε αυτήν τη λειτουργία στο ολόκληρο τον πίνακα, εκτελέστε την παραπάνω διαδικασία στα αριστερά και δεξιά διαστήματα αντίστοιχα.
2. Γρήγορη ταξινόμηση των δύο υποσυστοιχιών αναδρομικά έως ότου το μήκος κάθε υποπίνακα είναι 0 ή 1, οπότε οι πίνακες ταξινομούνται.
3. Δεδομένου ότι οι υποσυστοιχίες έχουν ταξινομηθεί χωριστά κατά τη διάρκεια της αναδρομής, δεν απαιτείται επιπλέον βήμα συγχώνευσης.

2. Εφαρμογή κώδικα και λεπτομερής επεξήγηση

Ο κωδικός κλειδιού για γρήγορη ταξινόμηση είναι如何根据基准元素划分数组区间(parttion), υπάρχουν πολλές μέθοδοι αποσύνθεσης, μόνο μία μέθοδος παρέχεται εδώ.挖坑法
Κώδικας:

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, δηλαδή, δεν χρειάζεται να συνεχιστεί η αποσύνθεση αυτή τη στιγμή χρόνος.

2. Γιατί να πάει πρώτα η δεξιά αντί για την αριστερά;

Εξαρτάται από το ποιος θα πάει πρώτος基准元素的位置,Στον παραπάνω κώδικα, το βασικό στοιχείο (κλειδί) είναι το πιο αριστερό στοιχείο εάν μετακινηθεί πρώτοleft, αριστερά συναντά πρώτα ένα στοιχείο μεγαλύτερο από το βασικό στοιχείο και μετά εκτελείarr[right] = arr[left], λόγω μη αποθήκευσηςarr[right], αυτό το στοιχείο θα χαθεί
Αν πάτε πρώτα δεξιά, το δεξι πρώτα συναντά ένα στοιχείο μικρότερο από το βασικό στοιχείο και μετά εκτελείταιarr[left]=arr[right], επειδή το αριστερό δεν έχει μετακινηθεί αυτήν τη στιγμή, εξακολουθεί να είναι το pivot, αλλά το pivot αποθηκεύτηκε από εμάς χρησιμοποιώντας το κλειδί.

3. Γιατί είναι arr[right]>=key;>Δεν είναι δυνατό;

Μεγαλύτερο ή ίσο με είναι κυρίως για επεξεργασία重复元素问题
Για παράδειγμα, υπάρχει ένας πίνακας[6,6,6,6,6]Εάν είναι >, ο δεξιός δείκτης δεν θα μετακινηθεί, ούτε ο αριστερός δείκτης θα μετακινηθεί και θα κολλήσει σε έναν άπειρο βρόχο.

4. Γιατί ονομάζεται μέθοδος εκσκαφής λάκκου;

Όταν ο δείκτης r συναντήσει τον πρώτοarr[r] = arr[l], αυτή τη στιγμή, η θέση l είναι κενή, σχηματίζοντας ένα κοίλωμα.

---

3. Βελτιστοποίηση γρήγορης ταξινόμησης

Υπάρχουν δύο κύριες κατευθύνσεις βελτιστοποίησης:

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 δεν μπορεί να δείχνει σε αυτά τα δύο στοιχεία και πρέπει να είναι εκτός του διαστήματος
• Ο λεγόμενος πίνακας χωρίζεται σε τρία μέρη, που σημαίνει χρήση三个指针去分别维护四个区间, ένα από τα διαστήματα είναι未处理区间, καθώς ο δείκτης cur συνεχίζει να κινείται, όλα τα διαστήματα υποβάλλονται σε επεξεργασία και τελικά υπάρχουν μόνο τρία διαστήματα.

Εφαρμόστε τις παραπάνω ιδέες σε快速排序的parttion中, το τελικό αποτέλεσμα χωρίζεται σε τρία διαστήματα

Κώδικας:

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.Το Kth μεγαλύτερο στοιχείο στον πίνακα
Σύνδεσμος: https://leetcode.cn/problems/kth-largest-element-in-an-array/
αναλύει

• Η λύση της ωμής βίας είναι να το χρησιμοποιήσετε απευθείαςsortΤαξινόμηση και μετά επιστροφή στο Kth μεγαλύτερο
• χρονική πολυπλοκότητα: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)