Maîtrisez rapidement l'algorithme de tri Java - tri rapide (image et texte)

Concept

Le tri rapide est un tri par échange L'étape principale est d'utiliser l'élément de référence à des fins de comparaison, et placez les éléments qui sont plus petits que l'élément de référence. Ceux qui sont plus grands que l'élément de base se déplacent d'un côté et ceux qui sont plus grands que l'élément de base se déplacent de l'autre côté. Ainsi, le réseau est divisé en deux parties, puis les éléments de référence sont sélectionnés parmi les deux parties et les étapes ci-dessus sont répétées. Le processus est le suivant :

(Vidéo recommandée : Tutoriel vidéo Java)

Violet : élément de base
Vert : supérieur à l'élément de base
Jaune : moins que les éléments de base

Cette idée est appelée la méthode diviser pour régner.

Élément de base

La sélection de l'élément de base peut être sélectionnée au hasard. Dans l'utilisation suivante, j'utiliserai le premier élément comme élément de base.

Le processus de tri

Le processus de tri et de fractionnement est le suivant :

Le violet est l'élément de base (resélectionné à chaque tour)
Le vert est les autres éléments

Premier tour

Deuxième tour

Troisième tour

Comme le montre la figure ci-dessus :

Si le nombre d'éléments est n, car le processus de tri doit être comparé à tous les éléments, la complexité temporelle est O (n),
En moyenne, les tours de tri nécessitent des tours de connexion, donc la complexité temporelle moyenne du tri rapide est O(nlogn).

Les méthodes de mise en œuvre du tri

Les méthodes de mise en œuvre comprennent la méthode de circulation bilatérale et la méthode de circulation unilatérale

Méthode de circulation bilatérale

Le premier choix est de sélectionner l'élément pivot (pivot) 4, et de placer les pointeurs gauche et droit pour qu'ils pointent vers les éléments les plus à gauche et à droite du tableau, comme suit :

Premier Dans cette boucle, commencez par les données pointées par le pointeur droit (rightData) et comparez-les avec l'élément de base
Si rightData >= pivot, alors le pointeur droit se déplace vers la gauche . Si rightData Les données pointées par le pointeur gauche (leftData) sont comparées à l'élément de référence. Si leftData pivot, le pointeur gauche se déplace vers. la droite. Si leftData > pivote, les éléments pointés par left et right sont échangés.

Après le premier tour de mouvement du pointeur, la structure suivante est obtenue :

Ensuite, les éléments pointés par gauche et droite sont échangés :

Une fois le premier tour de boucle terminé, passez à nouveau au pointeur droit et répétez les étapes ci-dessus.

Après le deuxième tour, on obtient :

Après le troisième tour, on obtient :

Après le quatrième cycle, on obtient :

On juge que les pointeurs gauche et droit pointent vers le même élément, les pointeurs arrêtent de bouger, et le pivot et le pointeur les éléments sont échangés, on obtient :

déclare la fin du cycle et le divise en deux parties selon l'élément Pivot. Les tableaux de ces deux parties sont ensuite exploités en fonction. aux étapes ci-dessus.

Code d'implémentation

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;"><strong>Méthode de boucle unilatérale</strong></p><p>La méthode de boucle bilatérale compare et échange des éléments des deux côtés du tableau, et La règle de boucle unilatérale traverse d'un côté du tableau et compare et échange vers l'arrière, ce qui la rend plus facile à mettre en œuvre. <br>Le processus est le suivant : </p><blockquote><p>Tout d'abord, l'élément pivot est sélectionné (peut être sélectionné au hasard) <br>Définissez un pointeur de marque pour pointer vers la position de départ du tableau, représentant le limite de zone plus petite que l'élément pivot (je ne comprends pas, comprenez-le simplement comme quelque chose qui sera utilisé pour échanger des éléments plus tard) </p></blockquote><p>Le tableau d'origine est le suivant : </p><p><img src="https://img.php.cn/upload/article/000/000/040/b739c5c8ed7df91b0c77a8fae57a6150-11.jpg" alt="Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)"></p><blockquote><p>从基准元素下一位开始遍历数组<br>如果该元素大于基准元素，继续往下遍历<br>如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。</p></blockquote><p>遍历到元素3时，因为3 </p><p><img src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-12.jpg" alt="Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)"></p><p>然后交换元素</p><p><img src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-13.jpg" alt="Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)"></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>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!