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
Hintergrund
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.
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:
Element 3 als Drehpunkt auswählen
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));
}
}[1, 2, 3, 4, 6, 9]
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 ;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)
(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.
Das obige ist der detaillierte Inhalt vonMeituan-Interview: Bitte schreiben Sie einen kurzen Zeitplan von Hand, ich war schockiert!. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
