Das Sortieren ist eine der grundlegenden Arten von Aktivitäten oder Aktionen, die an Objekten ausgeführt werden. Schon in der Kindheit wird Kindern das Sortieren beigebracht und so ihr Denken entwickelt. Auch Computer und Programme sind keine Ausnahme. Es gibt eine große Vielfalt an Algorithmen. Ich schlage vor, dass Sie sich ansehen, was sie sind und wie sie funktionieren. Und was wäre, wenn Sie eines Tages in einem Vorstellungsgespräch nach einem dieser Punkte gefragt würden?
Einführung
Das Sortieren von Elementen gehört zu den Kategorien von Algorithmen, an die sich ein Entwickler gewöhnen muss. Früher, als ich studierte, wurde die Informatik nicht so ernst genommen, jetzt in der Schule sollte man in der Lage sein, Sortieralgorithmen umzusetzen und zu verstehen. Grundlegende Algorithmen, die einfachsten, werden mithilfe einer Schleife implementiert for. Um eine Sammlung von Elementen, beispielsweise ein Array, zu sortieren, müssen Sie diese Sammlung natürlich irgendwie durchlaufen. Zum Beispiel:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Was können Sie zu diesem Code sagen? Wir haben eine Schleife, in der wir den Indexwert ( int i) von 0 bis zum letzten Element im Array ändern. Im Wesentlichen nehmen wir einfach jedes Element im Array und geben seinen Inhalt aus. Je mehr Elemente das Array enthält, desto länger dauert die Ausführung des Codes. Das heißt, wenn n die Anzahl der Elemente ist, dauert die Ausführung des Programms bei n=10 doppelt so lange wie bei n=5. Wenn unser Programm eine Schleife hat, erhöht sich die Ausführungszeit linear: Je mehr Elemente, desto länger die Ausführung. Es stellt sich heraus, dass der Algorithmus des obigen Codes in linearer Zeit (n) läuft. In solchen Fällen wird die „Algorithmuskomplexität“ als O(n) bezeichnet. Diese Notation wird auch „big O“ oder „asymptotisches Verhalten“ genannt. Aber Sie können sich einfach an „die Komplexität des Algorithmus“ erinnern.
Die einfachste Sortierung (Bubble Sort)
Wir haben also ein Array und können darüber iterieren. Großartig. Versuchen wir nun, es in aufsteigender Reihenfolge zu sortieren. Was bedeutet das für uns? Das bedeutet, dass wir bei zwei gegebenen Elementen (z. B. a=6, b=5) a und b vertauschen müssen, wenn a größer als b ist (wenn a > b). Was bedeutet das für uns, wenn wir mit einer Sammlung nach Index arbeiten (wie es bei einem Array der Fall ist)? Das heißt, wenn das Element mit Index a größer als das Element mit Index b ist (Array[a] > Array[b]), müssen diese Elemente ausgetauscht werden. Ein Ortswechsel wird oft als Tausch bezeichnet. Es gibt verschiedene Möglichkeiten, den Ort zu wechseln. Aber wir verwenden einfachen, klaren und leicht zu merkenden Code:
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));for(int i =1; i < array.length; i++){if(array[i]< array[i -1]){swap(array, i, i-1);}}System.out.println(Arrays.toString(array));
Wie wir sehen können, haben die Elemente tatsächlich ihre Plätze gewechselt. Wir haben mit einem Element begonnen, weil... Wenn das Array nur aus einem Element besteht, gibt der Ausdruck 1 < 1 nicht „true“ zurück und so schützen wir uns vor Fällen eines Arrays mit oder ohne ein Element und der Code sieht besser aus. Aber unser letztes Array ist sowieso nicht sortiert, weil... Es ist nicht möglich, alle in einem Durchgang zu sortieren. Wir müssen eine weitere Schleife hinzufügen, in der wir die Durchgänge nacheinander ausführen, bis wir ein sortiertes Array erhalten:
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));boolean needIteration =true;while(needIteration){
needIteration =false;for(int i =1; i < array.length; i++){if(array[i]< array[i -1]){swap(array, i, i-1);
needIteration =true;}}}System.out.println(Arrays.toString(array));
Unsere erste Sortierung hat also funktioniert. Wir iterieren in der äußeren Schleife ( while), bis wir entscheiden, dass keine weiteren Iterationen erforderlich sind. Standardmäßig gehen wir vor jeder neuen Iteration davon aus, dass unser Array sortiert ist und wir keine weitere Iteration durchführen möchten. Deshalb gehen wir die Elemente der Reihe nach durch und überprüfen diese Annahme. Wenn die Elemente jedoch nicht in der richtigen Reihenfolge sind, tauschen wir die Elemente aus und stellen fest, dass wir nicht sicher sind, ob die Elemente jetzt in der richtigen Reihenfolge sind. Daher wollen wir eine weitere Iteration durchführen. Zum Beispiel [3, 5, 2]. 5 ist mehr als drei, alles ist in Ordnung. Aber 2 ist kleiner als 5. [3, 2, 5] erfordert jedoch einen weiteren Durchgang, weil 3 > 2 und sie müssen ausgetauscht werden. Da wir eine Schleife innerhalb einer Schleife verwenden, erhöht sich die Komplexität unseres Algorithmus. Bei n Elementen ergibt sich daraus n * n, also O(n^2). Diese Komplexität wird quadratisch genannt. Soweit wir wissen, können wir nicht genau wissen, wie viele Iterationen erforderlich sein werden. Der Algorithmuskomplexitätsindikator dient dazu, den Trend zunehmender Komplexität, den schlimmsten Fall, aufzuzeigen. Um wie viel erhöht sich die Laufzeit, wenn sich die Anzahl der Elemente n ändert? Die Blasensortierung ist eine der einfachsten und ineffizientesten Sortierungen. Manchmal wird es auch als „dummes Sortieren“ bezeichnet. Verwandtes Material:
Eine andere Sortierung ist die Auswahlsortierung. Es hat auch quadratische Komplexität, aber dazu später mehr. Die Idee ist also einfach. Bei jedem Durchgang wird das kleinste Element ausgewählt und an den Anfang verschoben. Beginnen Sie in diesem Fall jeden neuen Durchgang, indem Sie sich nach rechts bewegen, d. h. der erste Durchgang – vom ersten Element, der zweite Durchgang – vom zweiten. Es wird so aussehen:
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));for(int left =0; left < array.length; left++){int minInd = left;for(int i = left; i < array.length; i++){if(array[i]< array[minInd]){
minInd = i;}}swap(array, left, minInd);}System.out.println(Arrays.toString(array));
Diese Sortierung ist instabil, weil Identische Elemente (im Hinblick auf das Merkmal, nach dem wir die Elemente sortieren) können ihre Position ändern. Ein gutes Beispiel findet sich im Wikipedia-Artikel: Sorting_by-selection . Verwandtes Material:
Auch die Einfügungssortierung hat quadratische Komplexität, da wir wieder eine Schleife innerhalb einer Schleife haben. Wie unterscheidet es sich von der Auswahlsortierung? Diese Sortierung ist „stabil“. Dies bedeutet, dass identische Elemente ihre Reihenfolge nicht ändern. Identisch hinsichtlich der Merkmale, nach denen wir sortieren.
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));for(int left =0; left < array.length; left++){// Den Wert des Elements abrufenint value = array[left];// Durch die Elemente bewegen, die vor dem gezogenen Element liegenint i = left -1;for(; i >=0; i--){// Wenn ein kleinerer Wert herausgezogen wird, verschieben Sie das größere Element weiterif(value < array[i]){
array[i +1]= array[i];}else{// Wenn das gezogene Element größer ist, stoppenbreak;}}// Den extrahierten Wert in den freigegebenen Speicherplatz einfügen
array[i +1]= value;}System.out.println(Arrays.toString(array));
Unter den einfachen Sortierungen gibt es noch eine weitere – die Pendelsortierung. Aber ich bevorzuge die Shuttle-Variante. Es scheint mir, dass wir selten über Space Shuttles sprechen und dass es sich beim Shuttle eher um einen Lauf handelt. Daher ist es einfacher, sich vorzustellen, wie Shuttles ins All geschossen werden. Hier ist eine Assoziation mit diesem Algorithmus. Was ist die Essenz des Algorithmus? Der Kern des Algorithmus besteht darin, dass wir von links nach rechts iterieren und beim Austauschen von Elementen alle anderen zurückbleibenden Elemente überprüfen, um festzustellen, ob der Austausch wiederholt werden muss.
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));for(int i =1; i < array.length; i++){if(array[i]< array[i -1]){swap(array, i, i -1);for(int z = i -1;(z -1)>=0; z--){if(array[z]< array[z -1]){swap(array, z, z -1);}else{break;}}}}System.out.println(Arrays.toString(array));
Eine weitere einfache Sortierung ist die Shell-Sortierung. Sein Wesen ähnelt der Blasensortierung, aber bei jeder Iteration entsteht eine andere Lücke zwischen den verglichenen Elementen. Bei jeder Iteration wird es halbiert. Hier ist eine Beispielimplementierung:
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));// Berechnen Sie die Lücke zwischen den überprüften Elementenint gap = array.length /2;// Solange es einen Unterschied zwischen den Elementen gibtwhile(gap >=1){for(int right =0; right < array.length; right++){// Verschieben Sie den rechten Zeiger, bis wir einen finden können// zwischen ihm und dem Element davor ist nicht genügend Platzfor(int c = right - gap; c >=0; c -= gap){if(array[c]> array[c + gap]){swap(array, c, c + gap);}}}// Lücke neu berechnen
gap = gap /2;}System.out.println(Arrays.toString(array));
Zusätzlich zu den angegebenen einfachen Sortierungen gibt es komplexere Sortierungen. Beispiel: Zusammenführungssortierung. Erstens wird uns die Rekursion zu Hilfe kommen. Zweitens wird unsere Komplexität nicht mehr quadratisch sein, wie wir es gewohnt sind. Die Komplexität dieses Algorithmus ist logarithmisch. Geschrieben als O(n log n). Also lasst uns das tun. Schreiben wir zunächst einen rekursiven Aufruf der Sortiermethode:
publicstaticvoidmergeSort(int[] source,int left,int right){// Wählen Sie ein Trennzeichen, d. h. Teilen Sie das Eingabearray in zwei Hälftenint delimiter = left +((right - left)/2)+1;// Diese Funktion rekursiv für die beiden Hälften ausführen (wenn wir teilen können(if(delimiter >0&& right >(left +1)){mergeSort(source, left, delimiter -1);mergeSort(source, delimiter, right);}}
Fügen wir nun eine Hauptaktion hinzu. Hier ist ein Beispiel unserer Supermethode mit Implementierung:
publicstaticvoidmergeSort(int[] source,int left,int right){// Wählen Sie ein Trennzeichen, d. h. Teilen Sie das Eingabearray in zwei Hälftenint delimiter = left +((right - left)/2)+1;// Diese Funktion rekursiv für die beiden Hälften ausführen (wenn wir teilen können(if(delimiter >0&& right >(left +1)){mergeSort(source, left, delimiter -1);mergeSort(source, delimiter, right);}// Erstelle ein temporäres Array mit der gewünschten Größeint[] buffer =newint[right - left +1];// Beginnend am angegebenen linken Rand jedes Element durchgehenint cursor = left;for(int i =0; i < buffer.length; i++){// Wir verwenden das Trennzeichen, um von der rechten Seite auf das Element zu zeigen// Wenn delimeter > right, dann gibt es auf der rechten Seite keine nicht hinzugefügten Elemente mehrif(delimiter > right || source[cursor]> source[delimiter]){
buffer[i]= source[cursor];
cursor++;}else{
buffer[i]= source[delimiter];
delimiter++;}}System.arraycopy(buffer,0, source, left, buffer.length);}
Lassen Sie uns das Beispiel ausführen, indem wir die mergeSort(array, 0, array.length-1). Wie Sie sehen, besteht das Wesentliche darin, dass wir als Eingabe ein Array verwenden, das den Anfang und das Ende des zu sortierenden Abschnitts angibt. Wenn die Sortierung beginnt, sind dies der Anfang und das Ende des Arrays. Als nächstes berechnen wir das Trennzeichen – die Position des Teilers. Wenn der Teiler das Array in zwei Teile teilen kann, nennen wir rekursive Sortierung für die Abschnitte, in die der Teiler das Array unterteilt hat. Wir bereiten ein zusätzliches Pufferarray vor, in dem wir den sortierten Abschnitt auswählen. Als nächstes platzieren wir den Cursor am Anfang des zu sortierenden Bereichs und beginnen, jedes Element des leeren Arrays, das wir vorbereitet haben, durchzugehen und es mit den kleinsten Elementen zu füllen. Wenn das Element, auf das der Cursor zeigt, kleiner ist als das Element, auf das der Divisor zeigt, platzieren wir dieses Element im Pufferarray und bewegen den Cursor. Andernfalls platzieren wir das Element, auf das das Trennzeichen zeigt, im Pufferarray und verschieben das Trennzeichen. Sobald das Trennzeichen über die Grenzen des sortierten Bereichs hinausgeht oder wir das gesamte Array füllen, gilt der angegebene Bereich als sortiert. Verwandtes Material:
Ein weiterer interessanter Sortieralgorithmus ist Counting Sort. Die algorithmische Komplexität beträgt in diesem Fall O(n+k), wobei n die Anzahl der Elemente und k der Maximalwert des Elements ist. Es gibt ein Problem mit dem Algorithmus: Wir müssen die minimalen und maximalen Werte im Array kennen. Hier ist eine Beispielimplementierung der Zählsortierung:
publicstaticint[]countingSort(int[] theArray,int maxValue){// Array mit „Zählern“ im Bereich von 0 bis zum Maximalwertint numCounts[]=newint[maxValue +1];// In der entsprechenden Zelle (Index = Wert) erhöhen wir den Zählerfor(int num : theArray){
numCounts[num]++;}// Array für sortiertes Ergebnis vorbereitenint[] sortedArray =newint[theArray.length];int currentSortedIndex =0;// das Array mit „counters“ durchgehenfor(int n =0; n < numCounts.length; n++){int count = numCounts[n];// gehe nach der Anzahl der Wertefor(int k =0; k < count; k++){
sortedArray[currentSortedIndex]= n;
currentSortedIndex++;}}return sortedArray;}
Soweit wir wissen, ist es sehr umständlich, wenn wir die Mindest- und Höchstwerte im Voraus kennen müssen. Und dann gibt es noch einen anderen Algorithmus – Radix Sort. Ich werde den Algorithmus hier nur visuell vorstellen. Zur Umsetzung siehe Materialien:
Nun, zum Nachtisch – einer der bekanntesten Algorithmen: schnelle Sortierung. Es hat algorithmische Komplexität, das heißt, wir haben O(n log n). Diese Sortierung wird auch Hoare-Sortierung genannt. Interessanterweise wurde der Algorithmus von Hoare während seines Aufenthalts in der Sowjetunion erfunden, wo er an der Moskauer Universität Computerübersetzung studierte und einen Russisch-Englisch-Sprachführer entwickelte. Dieser Algorithmus wird auch in einer komplexeren Implementierung in Arrays.sort in Java verwendet. Was ist mit Collections.sort? Ich schlage vor, Sie sehen selbst, wie sie „unter der Haube“ sortiert sind. Also der Code:
publicstaticvoidquickSort(int[] source,int leftBorder,int rightBorder){int leftMarker = leftBorder;int rightMarker = rightBorder;int pivot = source[(leftMarker + rightMarker)/2];do{// Verschiebe die linke Markierung von links nach rechts, während das Element kleiner als der Pivot istwhile(source[leftMarker]< pivot){
leftMarker++;}// Rechte Markierung verschieben, bis Element größer als Pivot istwhile(source[rightMarker]> pivot){
rightMarker--;}// Prüfen Sie, ob Sie Elemente, auf die Markierungen zeigen, nicht austauschen müssenif(leftMarker <= rightMarker){// Der linke Marker ist nur dann kleiner als der rechte Marker, wenn wir tauschen müssenif(leftMarker < rightMarker){int tmp = source[leftMarker];
source[leftMarker]= source[rightMarker];
source[rightMarker]= tmp;}// Markierungen verschieben, um neue Ränder zu erhalten
leftMarker++;
rightMarker--;}}while(leftMarker <= rightMarker);// Für Teile rekursiv ausführenif(leftMarker < rightBorder){quickSort(source, leftMarker, rightBorder);}if(leftBorder < rightMarker){quickSort(source, leftBorder, rightMarker);}}
Alles hier ist sehr beängstigend, also werden wir es herausfinden. Für die Eingabearray- int[]Quelle setzen wir zwei Markierungen, links (L) und rechts (R). Beim ersten Aufruf stimmen sie mit dem Anfang und dem Ende des Arrays überein. Als nächstes wird das tragende Element bestimmt, auch bekannt als pivot. Danach besteht unsere Aufgabe darin, Werte kleiner als pivotnach links pivotund größere nach rechts zu verschieben. Bewegen Sie dazu zunächst den Zeiger, Lbis wir einen Wert größer als finden pivot. Wenn kein kleinerer Wert gefunden wird, dann
L совпадёт с
pivot. Потом двигаем указатель
R пока не найдём меньшее, чем
pivot Bedeutung. Если меньшее Bedeutung не нашли, то
R совпадёт с
pivot. Далее, если указатель
L находится до указателя
R oder совпадает с ним, то пытаемся выполнить обмен элементов, если элемент
L меньше, чем
R. Далее
L сдвигаем вправо на 1 позицию,
R сдвигаем влево на одну позицию. Когда левый маркер
L окажется за правым маркером
R это будет означать, что обмен закончен, слева от
pivot меньшие значения, справа от
pivot — большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая Sortierung, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а
Pivot по центру, т.е. число 6. Обведём его в круг. Под 4 напишем
L, под 3 напишем
R. 4 меньше чем 6, 2 меньше чем 6. Gesamt,
L переместился на положение
pivot, т.к. по условию
L не может уйти дальше, чем
pivot. Напишем снова 4 2 6 7 3 , обведём 6 вкруг (
pivot) и поставим под ним
L. Теперь двигаем указатель
R. 3 меньше чем 6, поэтому ставим маркер
R на цифру 3. Так Wie 3 меньше, чем
pivot 6 выполняем
swap, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему
pivot. Указатель
L на цифре 3, указатель
R на цифре 6. Мы помним, что двигаем указатели до тех пор, пока
L не зайдём за
R.
L двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1.
Предпоследня цифра 1: Сдвинули указатель
L на цифру 1, т.к. мы можем двигать
L до тех пор, пока указатель
L указывает на цифру, меньшую чем
pivot. А вот
R мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель
R указывает на цифру, которая больше чем
pivot.
swap не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим
pivot 6.
L сдвигается на
pivot и больше не двигается.
R тоже не двигается. Обмен не производим. Сдвигаем
L и
R на одну позицию и подписываем цифру 1 маркером
R, а
L получается вне числа. Т.к.
L вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем
pivot 6. Выделяем новый
pivot и начинаем всё снова )
Предпоследняя цифра 7: Сдвинули указать
L на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем
pivot, то делаем
swap. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он
pivot. Указатель
L теперь сдвигается на цифру 7, а указатель
R сдвигается на цифру 3. Часть от
L до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя
R отправляем на сортировку. Выбираем
pivot и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с
pivot значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, Wie такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая Sortierung не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до
pivot до того, Wie другой элемент попал в часть до
pivot при помощи обмена. Материал:
Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, Wie с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Wieим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так Wie это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой "
Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown —
AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на
sorting.at и
visualgo.net. Ну и весь Youtube к вашим услугам.
GO TO FULL VERSION