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

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

angryTom
Libérer: 2019-11-29 16:55:00
avant
3718 Les gens l'ont consulté

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

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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
Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

Deuxième tour
Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

Troisième tour
Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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 :
Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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 :

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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 :

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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 :

Maîtrisez rapidement lalgorithme de tri Java - tri rapide (image et texte)

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>
Copier après la connexion

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!

Étiquettes associées:
source:cnblogs.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal