Conseils et précautions de tri rapide Java

Maîtrisez les compétences et précautions clés de Java Quick Sort

Quick Sort est un algorithme de tri couramment utilisé. Son idée principale est de diviser la séquence à trier en deux parties indépendantes en sélectionnant un élément de référence, tous les éléments de. une partie est plus petite que l'élément de référence, et tous les éléments de l'autre partie sont supérieurs à l'élément de référence, puis les deux parties sont triées de manière récursive, et enfin une séquence ordonnée est obtenue.

Bien que la complexité temporelle du tri rapide soit O(nlogn) dans le cas moyen, elle dégénérera en O(n^2) dans le pire des cas, donc en utilisation réelle, nous devons maîtriser certaines compétences et précautions clés, pour améliorer l'efficacité du tri rapide.

1. Choisissez les éléments de référence appropriés :
   L'efficacité du tri rapide est affectée par le choix des éléments de référence. Habituellement, nous pouvons sélectionner le premier élément de la séquence à trier comme élément de référence, mais si la séquence à trier est déjà proche de l'ordre, cette méthode de sélection peut conduire au pire des cas de dégénérescence en O (n ^ 2 ). Afin d'éviter cette situation, vous pouvez sélectionner aléatoirement l'élément de référence ou sélectionner l'élément du milieu de la séquence à trier comme élément de référence.
2. Diviser les sous-séquences :
   Pendant le processus de division du tri rapide, nous devons diviser la séquence à trier en deux sous-séquences. Vous pouvez utiliser des pointeurs doubles, en commençant par les deux extrémités de la séquence à trier, et en déplaçant continuellement les pointeurs vers le milieu jusqu'à ce qu'ils se rencontrent, tout en échangeant les positions des éléments plus petits que l'élément de base et des éléments plus grands que l'élément de base. Enfin, insérez l'élément de base dans la position de rencontre pour compléter une division.
3. Appel récursif :
   Une fois la division terminée, nous obtenons deux nouvelles sous-séquences. A ce moment, il est nécessaire d’appeler récursivement un tri rapide sur les deux sous-séquences pour obtenir la séquence ordonnée finale. La condition de fin de l'appel récursif est que la longueur de la sous-séquence soit inférieure ou égale à 1.

Ce qui suit est un exemple de code pour montrer comment implémenter le tri rapide :

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 1, 4};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Dans le code ci-dessus, nous définissons la méthode quickSort pour effectuer un tri rapide. À l'intérieur de la méthode, nous sélectionnons d'abord le premier élément de la séquence à trier comme élément de référence, et le divisons en appelant la méthode partition. La méthode partition utilise des pointeurs doubles, en partant des deux extrémités de la séquence, en déplaçant les pointeurs vers le milieu jusqu'à ce qu'ils se rencontrent, et en échangeant les positions des éléments plus petits que l'élément de base et des éléments plus grands que l'élément de base. . Enfin, insérez l'élément de base à l'endroit où il se rencontre. quickSort方法用于完成快速排序。在方法内部，我们首先选择待排序序列的第一个元素作为基准元素，并通过调用partition方法进行划分。partition方法使用双指针的方式，从序列的两端开始，不断向中间移动指针，直到相遇，并交换比基准元素小的元素和比基准元素大的元素的位置。最后，将基准元素插入到相遇的位置。

在main方法中，我们测试了该快速排序算法。输出结果为1 2 3 4 5

Dans la méthode main, nous avons testé l'algorithme de tri rapide. Le résultat de sortie est 1 2 3 4 5, indiquant que le tri est correct.

En maîtrisant les compétences clés et les précautions ci-dessus, nous pouvons mieux comprendre et appliquer l'algorithme de tri rapide, améliorant ainsi l'efficacité et la précision du tri. Dans le même temps, dans le développement réel, nous pouvons optimiser davantage l'algorithme, par exemple en utilisant la méthode à trois chiffres pour sélectionner les éléments de référence afin d'éviter le pire des cas. Bref, le tri rapide est un algorithme de tri très pratique et efficace qui mérite d’être maîtrisé et étudié en profondeur. 🎜

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!