Einfaches Beispiel für eine schnelle Sortierung in Java

In diesem Artikel werden hauptsächlich einfache Java-Sortierbeispiele im Detail vorgestellt, die einen bestimmten Referenzwert haben

Grundkonzepte

Finden ein Element (theoretisch können Sie jedes finden) als Pivot (Pivot) und dann das Array so aufteilen, dass der Wert des Elements auf der linken Seite des Pivots nicht größer ist als der Pivot-Wert und der Wert des Elements auf der rechten Seite des Drehpunkts ist nicht kleiner als der Basiswert, damit das Basiselement nach dem Sortieren an die richtige Position angepasst wird. Durch die rekursive Schnellsortierung werden die anderen n-1 Elemente nach dem Sortieren an die richtige Position gebracht. Schließlich befindet sich jedes Element nach dem Sortieren an der richtigen Position und die Sortierung ist abgeschlossen. Daher ist der Kernalgorithmus des Schnellsortierungsalgorithmus die Partitionsoperation, d. h. wie die Position des Benchmarks angepasst wird und wie die endgültige Position des zurückgegebenen Benchmarks für die Divide-and-Conquer-Rekursion angepasst wird.

2. Referenzelement auswählen

1. Referenzelement korrigieren

Wenn die Eingabereihenfolge zufällig ist, ist die Verarbeitungszeit akzeptabel. Wenn das Array bereits sortiert ist, ist die Aufteilung zu diesem Zeitpunkt eine sehr schlechte Aufteilung. Da jede Unterteilung die zu sortierende Reihenfolge nur um eins reduzieren kann, ist dies das schlimmste Szenario, bei dem die schnelle Sortierung zur Blasensortierung wird und die zeitliche Komplexität Θ(n^2) beträgt. Darüber hinaus ist es durchaus üblich, dass die Eingabedaten geordnet oder teilweise geordnet sind. Daher ist die Verwendung des ersten Elements als Basiselement sehr schlecht und sollte sofort aufgegeben werden.

2. Zufälliges Basiselement

Dies ist eine relativ sichere Strategie. Da die Position des Referenzelements zufällig ist, ist die resultierende Segmentierung nicht immer eine Segmentierung von schlechter Qualität. Wenn alle Array-Nummern gleich sind, ist dies immer noch der schlimmste Fall und die Zeitkomplexität beträgt O(n^2). Tatsächlich beträgt die Wahrscheinlichkeit, Quicksort zu randomisieren, um den theoretisch schlechtesten Fall zu erhalten, nur 1/(2^n). Daher kann die zufällige Schnellsortierung für die meisten Eingabedaten die erwartete Zeitkomplexität von O(n×log(n)) erreichen.

3. Finden Sie den Mittelwert von drei Zahlen.

Die beste Aufteilung besteht darin, die zu sortierende Folge in Teilfolgen gleicher Länge zu unterteilen Folge, also die N/2-te Zahl. Dies ist jedoch schwer zu berechnen und wird Quicksort erheblich verlangsamen. Eine solche Schätzung des Medians kann durch zufällige Auswahl dreier Elemente und Verwendung ihres Medians als Basiselement erhalten werden. Tatsächlich hilft Zufälligkeit nicht viel, daher besteht der allgemeine Ansatz darin, den Median der drei Elemente am linken Ende, am rechten Ende und in der Mittelposition als Basiselement zu verwenden.

3. Partitionsalgorithmus

Der Partitionsalgorithmus ist der Kern der Schnellsortierung, Sie können diesen Algorithmus zuerst erlernen. Fügen Sie zuerst den Code ein:

  public int partition(int[] num,int left,int right){
    if(num==null || num.length<=0 || left<0 || right>=num.length){
      return 0;
    }
    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标
    while (left<=right){         //从两端交替向中间扫描
      while (num[left]<prio)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最终将基准数归位 
        left++;
        right--;
      }
    }
    return left;
  }

Die Idee dieser Methode besteht darin, zuerst ein Pivot-Element zu finden (das erste Element wird in der Implementierung dieser Methode gefunden). Es gibt tatsächlich viele Details. Der Artikel wird die Beschreibung hier vereinfachen und dann zwei Zeiger links und rechts von beiden Seiten des Arrays generieren (das genaue Wohin wird durch die übergebenen Parameter bestimmt. Jedes Mal, wenn es gefunden wird). Das Element links ist größer als das Pivotelement, i stoppt, und das Element rechts stoppt. Wenn das Element kleiner als das Pivotelement j ist, stoppt es und die Positionen der beiden Zahlen werden vertauscht. Bis sich die beiden Zeiger links und rechts treffen. Setzen Sie dann das Drehelement in die linke Position ein, wo es sein sollte.

Das Endergebnis besteht darin, dass der [linke, rechte] Teil des Arrays in zwei Teilen erscheint. Die endgültige Position des Pivot-Elements auf der linken Seite ist kleiner oder gleich dem Pivot-Element und Die Endposition rechts ist größer oder gleich dem Pivotelement. Das Schwenkelement wird in einer absolut korrekten Position eingesetzt.

4. Implementierung des Sortieralgorithmus

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一个数组中取一个基准数字，把小的数放基准的左边，大的数放基准的右边。
 * 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字，小的放左边，大的放右边。
 * 这个里面用到的递归。我们需要三个参数，一个是数组，另外两个是序列的边界
 * @author HJS
 */
public class QuickSort{

  void sort(int num[],int left,int right){
    if (left
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonEinfaches Beispiel für eine schnelle Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!