Heute hat mich der Interviewer gebeten, vor Ort eine kurze Sortierung zu schreiben. Die Szene sieht wie folgt aus:
Interviewer: Lassen Sie uns weiter über Datenstrukturen und Algorithmen sprechen. (Während er sprach, drehte er meinen Lebenslauf um und reichte mir einen Stift, was bedeutete, dass er mich aufforderte, auf die Rückseite meines Lebenslaufs zu schreiben)
Neuling ich: Was meinst du? Hier schreiben? (Zeigt auf den Lebenslauf)
Interviewer: Ja
Rookie-Ich: Nein
Interviewer: Okay, das ist alles für das heutige Interview
Rookie-Ich: (Ich bin sehr wütend, ich möchte es auf meine Arbeitsverwaltung setzen Lebenslauf: Code schreiben? Schreiben Sie einfach, es ist sowieso nur ein Stück Papier.
Obwohl das schnelle Anstehen einfach ist, schätze ich, dass viele Leute es nicht von Hand schreiben können. Gibt es viele Leute, die es auf verschiedene Weise von Hand schreiben können?
Ich bin ein Neuling, kann aber immer noch mit der Hand schreiben. Schließlich habe ich vor dem Vorstellungsgespräch einfach bewusst „
Schnelles Schreiben per Diktat
“ vorbereitet. Lassen Sie uns nun analysieren und analysieren ---- schnelle Sortierung.
Hintergrund
Aus der Enzyklopädie: Schnellsortierung wurde 1962 von C. A. R. Hoare vorgeschlagen. Seine Grundidee besteht darin, die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile zu unterteilen. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil und dann wird diese Methode verwendet, um die beiden Teile der Daten schnell zu trennen . Beim Sortieren kann der gesamte Sortiervorgang [rekursiv] durchgeführt werden, sodass die gesamten Daten zu einer geordneten Reihenfolge werden.
Es ist ziemlich schwierig, dieses Konzept zu verstehen.
Es kann so verstanden werden:
Quick Sort ist eine verbesserte Version von Bubble Sort. Der gesamte Prozess besteht darin, Dinge zu entfernen und zu flicken, sie abzureißen und zu flicken, sie abzureißen und zu flicken, bis Alle Elemente erreichen einen geordneten Zustand.
Kernidee:
Nehmen Sie zunächst eine Zahl aus der Folge als Basiszahl und führen Sie dann eine Größenpartitionierung durch.
Beim Partitionierungsprozess werden alle Zahlen, die größer als diese Zahl sind, rechts davon platziert und Zahlen kleiner als oder gleich sind. Platzieren Sie sie alle auf der linken Seite.
Wiederholen Sie den zweiten Schritt für die linken und rechten Intervalle, bis in jedem Intervall nur noch eine Zahl vorhanden ist und die Sortierung abgeschlossen ist.
Umsetzungsfall
Lass es uns Schritt für Schritt anhand von Bildern und Texten abbauen.
Nehmen [4,1,6,2,9,3]dieses Array als Beispiel.
Erster Durchgang:
- Erst [4,1,6,2,9,3] teilen und Element 4 als Drehpunkt auswählen
- Überprüfen Sie, ob 1 < (Pivotpunkt)
- Überprüfen Sie, ob 2 < 4 (Pivotpunkt)
- 2 < 4 (Pivotpunkt) wahr ist, tauschen Sie Index 2 mit gespeichertem Index 6 aus
Überprüfen Sie, ob 9 < 4 (Pivotpunkt) Prüfen Sie, ob 3 < 4 (Pivotpunkt) 3 < 4 (Pivotpunkt) Wenn wahr, Index 3 und 6 speichern. Tauschen Sie Pivotpunkt 4 und Speicherung aus Index 3Zu diesem Zeitpunkt ist die linke Seite von Pivotpunkt 4 alle kleiner als 4 und die rechte Seite ist größer als 4
-
Die aktuelle Array-Reihenfolge ist [3, 1, 2, 4, 9, 6].
- Nächster Schritt:
Zuerst die linke Seite sortieren
Element 3 als Drehpunkt auswählen
Überprüfen Sie, ob 1 < (Drehpunkt)Tausch Pivotpunkt 3 und Speicherindexwert 2Jetzt wurde der Pivotpunkt an der sortierten Position geteilt[2,1] Wählen Sie 2 als Pivotpunkt-
Überprüfen Sie, ob 1 < 2 (Drehpunkt)Die Durchquerung auf der linken Seite ist abgeschlossen und der Drehpunkt 2 und der Speicherindex 1 sind vertauschtDas Gleiche gilt für die rechte ... vermeiden Sie Visuals Ich werde die Müdigkeit nicht einzeln beschreiben, aber Sie können das dynamische Demonstrationsbild unten sehen. 2. Der gesamte Prozess der Schnellsortiermethode. 3. Code-Implementierung: import java.util.Arrays;
public class QuickSortDemo {
//四个步骤：
//1.比较startIndex和endIndex，更喜欢理解为校验
//2.找出基准
//3.左边部分排序
//4.右边排序
public static void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex < endIndex) {
//找出基准
int partition = partition(arr, startIndex, endIndex);
//分成两边递归进行
quickSort(arr, startIndex, partition - 1);
quickSort(arr, partition + 1, endIndex);
}
}
//找基准
private static int partition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
//等于就没有必要排序
while (left != right) {
while (left < right && arr[right] > pivot) {
right--;
}
while (left < right && arr[left] <= pivot) {
left++;
}
//找到left比基准大，right比基准小，进行交换
if (left < right) {
swap(arr, left, right);
}
}
//第一轮完成，让left和right重合的位置和基准交换，返回基准的位置
swap(arr, startIndex, left);
return left;
}
//两数交换
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] a = {3, 1, 2, 4, 9, 6};
quickSort(a, 0, a.length - 1);
//输出结果
System.out.println(Arrays.toString(a));
}
}Nach dem Login kopieren
[1, 2, 3, 4, 6, 9]
Nach dem Login kopieren
-
Es gibt mehrere Möglichkeiten, Quick Sort zu schreiben. Wenn Sie interessiert sind, können Sie auch selbst nachschlagen, wie Quick Sort in Wikipedia eingeführt wird. 4. Komplexitätsanalyse Reihenfolge jedes Mal ein Element)
In diesem Fall ist die zeitliche Komplexität leicht zu berechnen, nämlich die zeitliche Komplexität der Blasensortierung: T[n] = n * (n-1) = n^2 + n ; Der beste Fall ist O(nlog2n), der Ableitungsprozess ist wie folgt:
(Zeitkomplexitätsformel des rekursiven Algorithmus: T[n] = aT[n/b] + f(n) )
https://img2018.cnblogs.com/blog/1258817/201903/1258817-20190326191158640-601403776.pngDie durchschnittliche Zeitkomplexität beträgt also O(nlog2n)
Raumkomplexität: Der Raum Bei der Schnellsortierung wird O(1) verwendet, was eine konstante Ebene ist; und was wirklich Platz verbraucht, ist der rekursive Aufruf, da jede Rekursion einige Daten beibehalten muss: Im optimalen Fall beträgt die Platzkomplexität:
O(log2n ); Wenn die Gruppe jedes Mal gleichmäßig aufgeteilt ist
Die Raumkomplexität im schlimmsten Fall ist: O(n); sie degeneriert in den Fall der Blasensortierung
Die durchschnittliche Raumkomplexität ist also O (log2n)
5. Zusammenfassung der Schnellsortiermethode
Das erste Element wird standardmäßig als Pivotpunkt verwendet (die Bestätigung des Pivotpunkts unterscheidet zwischen „Schnellsortiermethode“ und „Zufallssortiermethode“). Zwei Algorithmen: während beim zufälligen Sortieren ein Element zufällig als Drehpunkt ausgewählt wird;
Wenn zwei nicht benachbarte Elemente ausgetauscht werden, können mehrere umgekehrte Reihenfolgen mit einem Austausch eliminiert werden, was den Sortiervorgang beschleunigt.
Postscript
-
Abschließend: Glauben Sie, dass schnelles Sortieren bei der Arbeit nützlich ist? Ich habe es nach fast zehn Jahren Arbeit noch nie benutzt, aber ich kenne die Idee der schnellen Warteschlange. Wenn ich mich nicht auf das Vorstellungsgespräch vorbereite, kann ich es sowieso nicht schreiben. Was ist mit Ihnen?
