Beherrschen Sie schnell den Java-Sortieralgorithmus - schnelle Sortierung (Bild und Text)

Konzept

Schnellsortierung ist eine Austauschsortierung. Der Hauptschritt besteht darin, das Basiselement zum Vergleich zu verwenden. und platzieren Sie die Elemente, die kleiner als das Basiselement sind. Die Elemente, die größer als das Basiselement sind, werden auf eine Seite verschoben, und diejenigen, die größer als das Basiselement sind, werden auf die andere Seite verschoben. Daher wird das Array in zwei Teile geteilt, und dann werden die Referenzelemente aus den beiden Teilen ausgewählt und die obigen Schritte werden wiederholt. Der Prozess ist wie folgt:

(Empfohlenes Video: Java-Video-Tutorial)

Lila: Benchmark-Element
Grün: Größer als Benchmark-Element
Gelb: weniger als Basiselemente

Diese Idee wird als Divide-and-Conquer-Methode bezeichnet.

Grundelement

Die Auswahl des Grundelements ist beliebig. In der folgenden Verwendung verwende ich das erste Element als Basiselement.

Der Sortiervorgang

Der Sortier- und Aufteilungsprozess ist wie folgt:

Lila ist das Basiselement (neu ausgewählt). in jeder Runde)
Grün ist andere Elemente

Erste Runde

Zweite Runde

Dritte Runde

Wie in der Abbildung oben gezeigt:

Wenn die Anzahl der Elemente n ist, beträgt die zeitliche Komplexität O, da der Sortierprozess mit allen Elementen verglichen werden muss (n),
Im Durchschnitt erfordern Sortierrunden logn-Runden, sodass die durchschnittliche Zeitkomplexität der schnellen Sortierung O(nlogn) beträgt.

Die Implementierungsmethoden der Sortierung

Die Implementierungsmethoden umfassen die bilaterale Zirkulationsmethode und die unilaterale Zirkulationsmethode

Bilaterale Zirkulationsmethode

Die erste Möglichkeit besteht darin, das Pivot-Element (Pivot) 4 auszuwählen und die Zeiger nach links und rechts so zu setzen, dass sie auf die Elemente ganz links und ganz rechts im Array zeigen, wie folgt:

Zuerst: Beginnen Sie in dieser Schleife zunächst mit den Daten, auf die der rechte Zeiger (rightData) zeigt, und vergleichen Sie sie mit dem Basiselement.
Wenn rightData >= Pivot, dann bewegt sich der rechte Zeiger nach links . Wenn rightData Pivot ist, werden die Elemente, auf die left und right zeigen, ausgetauscht.

Nach der ersten Runde der Zeigerbewegung ergibt sich folgende Struktur:

Dann werden die Elemente, auf die links und rechts zeigen, ausgetauscht:

Nachdem die erste Runde der Schleife beendet ist, wechseln Sie erneut zum rechten Zeiger und wiederholen Sie die obigen Schritte.

Nach der zweiten Runde erhalten Sie:

Nach der dritten Runde erhalten Sie:

Nach dem vierten Zyklus erhalten wir:

Es wird beurteilt, dass der linke und der rechte Zeiger auf dasselbe Element zeigen, die Zeiger aufhören, sich zu bewegen, und der Drehpunkt und der Zeiger Elemente ausgetauscht werden, erhalten wir:

erklärt das Ende des Zyklus und teilt ihn entsprechend dem Pivot-Element in zwei Teile. Die Arrays dieser beiden Teile werden dann entsprechend bearbeitet zu den oben genannten Schritten.

Implementierungscode

public class DoubleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left = pivot) {
                right--;
            }

            // 控制left指针比较并右移
            while (left <p id="单边循环法" style="white-space: normal;">Einseitige Schleifenmethode<strong></strong></p>Bilaterale Schleifenmethode vergleicht und tauscht Elemente von beiden Seiten des Arrays aus, und Die einseitige Schleifenregel verläuft von einer Seite des Arrays und vergleicht und tauscht rückwärts aus, was die Implementierung erleichtert. <p>Der Prozess ist wie folgt: <br></p><blockquote>Zuerst wird das Pivot-Element ausgewählt (kann zufällig ausgewählt werden) <p>Setzen Sie einen Markierungszeiger, der auf die Startposition des Arrays zeigt und das darstellt Bereichsgrenze kleiner als das Pivot-Element (verstehe es nicht. Verstehe es einfach als etwas, das später zum Austauschen von Elementen verwendet wird) <br></p>
</blockquote>Das ursprüngliche Array lautet wie folgt: <p></p><p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/b739c5c8ed7df91b0c77a8fae57a6150-11.jpg" class="lazy" alt="Beherrschen Sie schnell den Java-Sortieralgorithmus - schnelle Sortierung (Bild und Text)"></p><blockquote><p>从基准元素下一位开始遍历数组<br>如果该元素大于基准元素，继续往下遍历<br>如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。</p></blockquote><p>遍历到元素3时，因为3 </p><p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-12.jpg" class="lazy" alt="Beherrschen Sie schnell den Java-Sortieralgorithmus - schnelle Sortierung (Bild und Text)"></p><p>然后交换元素</p><p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-13.jpg" class="lazy" alt="Beherrschen Sie schnell den Java-Sortieralgorithmus - schnelle Sortierung (Bild und Text)"></p><p>然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。</p><p id="实现代码-1"   style="max-width:90%"><strong>实现代码</strong></p><pre class="brush:php;toolbar:false">public class SingleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 分治（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int mark = startIndex;

        for(int i = startIndex + 1; i<p id="总结" style="white-space: normal;"><strong>总结</strong></p><p>本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。</p><p>参考资料：《小灰的算法之旅》 第四章。</p><p>本文来自php中文网，<a href="https://www.php.cn/java/base/" target="_blank">java教程</a>栏目，欢迎学习！  </p>

Das obige ist der detaillierte Inhalt vonBeherrschen Sie schnell den Java-Sortieralgorithmus - schnelle Sortierung (Bild und Text). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!