Implémenter et améliorer l'algorithme de tri rapide de Java

Mise en œuvre et optimisation de l'algorithme de tri rapide Java

Quick Sort est un algorithme de tri classique qui a un large éventail d'applications dans des applications pratiques. Cet article présentera l'implémentation de l'algorithme de tri rapide en Java et améliorera l'efficacité de l'algorithme grâce à l'optimisation.

1. Principe de l'algorithme de tri rapide
   Le tri rapide adopte l'idée de diviser pour régner. L'idée de base est de diviser la séquence à trier en deux parties via un "benchmark", une partie est plus petite que le benchmark. , l'autre partie est plus grande que le benchmark, puis les deux parties sont divisées en deux parties. Le tri rapide est effectué de manière récursive, et enfin la séquence entière est triée.

Le processus spécifique de mise en œuvre est le suivant :

• Sélectionnez un élément de référence, généralement le premier élément de la séquence.
• Définissez deux pointeurs bas et haut pour pointer respectivement vers la tête et la queue de la séquence.
• Commencez par le haut, recherchez vers l'avant pour trouver un élément plus petit que la ligne de base et déplacez-le vers la position basse ; puis commencez par le bas, recherchez vers l'arrière pour trouver un élément plus grand que la ligne de base et déplacez-le vers la position haute.
• Répétez le processus ci-dessus jusqu'à ce que les niveaux bas et haut se rencontrent.
• Mettez l'élément de base en position de rencontre. À ce stade, les éléments à gauche de l'élément de base sont plus petits que lui et les éléments à droite sont plus grands que lui.
• Appelez un tri rapide de manière récursive sur les parties gauche et droite de l'élément de référence.

2. Implémentation Java de l'algorithme de tri rapide
   Ce qui suit est un exemple de code pour implémenter l'algorithme de tri rapide en Java :

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 = {6, 1, 9, 0, 4, 7, 8, 2, 5, 3};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

Ce qui précède est l'implémentation de base de l'algorithme de tri rapide, et les résultats du tri peuvent être testés via la méthode principale.

3. Optimisation de l'algorithme de tri rapide
   Bien que l'algorithme de tri rapide ait en moyenne une efficacité élevée, dans certains cas, son efficacité diminue. Afin d'améliorer l'efficacité de l'algorithme de tri rapide, les mesures d'optimisation suivantes peuvent être prises :

• Sélectionner aléatoirement l'élément de base : Afin d'éviter que l'élément de base sélectionné soit la plus grande ou la plus petite valeur de la séquence. , vous pouvez réduire cette possibilité en sélectionnant aléatoirement l'élément de base sexe.
• Méthode du milieu à trois nombres : La sélection de l'élément de référence peut être réalisée par la valeur médiane des trois nombres de la séquence. Sélectionnez les éléments de tête, du milieu et de queue de la séquence, disposez-les dans l'ordre du plus petit au plus grand et prenez la valeur du milieu comme élément de référence.

Grâce à l'optimisation ci-dessus, la complexité temporelle de l'algorithme de tri rapide peut être réduite dans des circonstances particulières et l'efficacité de l'algorithme de tri rapide peut être améliorée.

Résumé :
Cet article présente l'implémentation et l'optimisation de l'algorithme de tri rapide en Java. L'algorithme de tri rapide divise la séquence en sélectionnant des éléments de référence, puis trie de manière récursive les sous-séquences divisées pour finalement obtenir une séquence ordonnée. L'efficacité de l'algorithme de tri rapide peut être encore améliorée en sélectionnant aléatoirement des éléments de référence ou en utilisant des mesures d'optimisation telles que la méthode à trois nombres.

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!