Ausführliche Erläuterung der Vergleichssortierung und der Schnellsortierung

Quick Sort (kurz Quick Sort) wird aufgrund seiner hohen Effizienz (durchschnittliches O(nlogn)) häufig in schriftlichen Prüfungsfragen getestet.

Der erste Schritt zum schnellen Sortieren besteht darin, eine „Basis“ auszuwählen, die zum Vergleich und Austausch mit anderen Zahlen verwendet wird. Die Wahl dieser „Basis“ wirkt sich auf die Effizienz der schnellen Sortierung aus, aber wenn Sie die Basis um der Basis willen wählen, wird das Pferd von hinten aufgezäumt. Um beispielsweise die optimale Basis zu finden, müssen Sie den Median in der gesamten zu sortierenden Sequenz finden, aber das Finden des Medians ist tatsächlich sehr kostspielig. Die Wahl der Basis ist normalerweise das erste Objekt, das mittlere Objekt oder das letzte Objekt in der zu sortierenden Reihenfolge. In diesem Artikel wird die Auswahl des ersten Elements als Beispiel für eine kurze Analyse und Implementierung der Schnellsortierung verwendet.

Wählen Sie am Beispiel der zu sortierenden Spalte {6, 5, 3, 1, 7, 2, 4} das erste Element 6 als Basis aus.

Nachdem Sie die Basis ausgewählt haben, müssen Sie die Array-Elemente vergleichen und mit ihnen austauschen. Der zweite Schritt der Schnellsortierung besteht darin, einen „Sentinel“ für das erste und das letzte Element des Arrays festzulegen.

Nachdem Sie die Basis ausgewählt und den Wächter eingestellt haben, besteht der nächste Schritt darin, den Vergleich zu starten. Platzieren Sie die Basis mit dem Der letzte Sentinel j wird zuerst verglichen, und wenn er größer als Sentinel j ist, wird er mit Sentinel i+1 ausgetauscht.

Zu diesem Zeitpunkt wird die Basis nicht mehr mit Sentinel j verglichen, sondern mit Sentinel i. Wenn die Basis größer als Sentinel i ist, bewegt sich der Sentinel rückwärts, bis er es ist Bisher wurde Sentinel J-1 gleichzeitig ausgetauscht.

Wiederholen Sie die obigen Schritte und vergleichen Sie die Basis mit Sentinel J.

Das Endergebnis zeigt, dass die Position von Sentinel i = die Position von Sentinel j ist. Zu diesem Zeitpunkt wird dieser Position der Basiswert zugewiesen.

Auf diese Weise sind die Zahlen auf der linken Seite der Basis 6 alle kleiner als diese und die Zahlen auf der rechten Seite alle größer als sie Um die gleichen Schritte für das linke und rechte Array auszuführen, um die Basis auszuwählen und Sentinel festzulegen, kann die Sortierung am Ende abgeschlossen werden.

　Java

 1 package com.algorithm.sort.quick; 2  3 import java.util.Arrays; 4  5 /** 6  * 快速排序 7  * Created by yulinfeng on 2017/6/26. 8  */ 9 public class Quick {10     public static void main(String[] args) {11         int[] nums = {6, 5, 3, 1, 7, 2, 4};12         nums = quickSort(nums, 0, nums.length - 1);13         System.out.println(Arrays.toString(nums));14     }15     16     /**17      * 快速排序18      * @param nums 待排序数组序列19      * @param left 数组第一个元素索引20      * @param right 数组最后一个元素索引21      * @return 排好序的数组序列22      */23     private static int[] quickSort(int[] nums, int left, int right) {24         if (left < right) {25             int temp = nums[left];    //基数26             int i = left;    //哨兵i27             int j = right;    //哨兵j28             while (i < j) {29                 while (i < j && nums[j] >= temp) {30                     j--;31                 }32                 if (i < j) {33                     nums[i] = nums[j];34                     i++;35                 }36                 while (i < j && nums[i] < temp) {37                     i++;38                 }39                 while (i < j) {40                     nums[j] = nums[i];41                     j--;42                 }43             }44             nums[i] = temp;45             quickSort(nums, left, i - 1);46             quickSort(nums, i + 1, right);47         }48         return nums;49     }50 }

　Python3

 1 #快速排序 2 def quick_sort(nums, left, right): 3     if left < right: 4         temp = nums[left]    #基数 5         i = left    #哨兵i 6         j = right    #哨兵j 7         while i < j: 8             while i < j and nums[j] >= temp: 9                 j -= 110             if i < j:11                 nums[i] = nums[j]12                 i += 113             while i < j and nums[i] < temp:14                 i += 115             if i < j:16                 nums[j] = nums[i]17                 j -= 118         nums[i] = temp19         quick_sort(nums, left, i - 1)20         quick_sort(nums, i + 1, right)21     22     return nums23 24 nums = [6, 5, 3, 1, 7, 2, 4]25 nums = quick_sort(nums, 0, len(nums) - 1)26 print(nums)

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung der Vergleichssortierung und der Schnellsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!