Stratégies et techniques pour améliorer l'efficacité de la fonction de tri rapide Java

Méthodes et techniques pour optimiser la fonction de tri rapide Java

Quicksort (Quicksort) est un algorithme de tri courant L'idée est d'effectuer le tri en divisant le tableau en deux sous-tableaux, plus petits et plus grands, puis de trier le sous-tableau. encore une fois pour obtenir un ordre global. Dans les applications pratiques, nous devons optimiser les performances de la fonction de tri rapide pour améliorer l'efficacité du tri. Ce qui suit présentera quelques méthodes et techniques pour optimiser la fonction de tri rapide et donnera des exemples de code spécifiques.

1. Sélectionner aléatoirement des éléments de référence
   La sélection d'éléments de référence dans un tri rapide a un impact important sur l'efficacité du tri. L'approche traditionnelle consiste à sélectionner le premier ou le dernier élément comme élément de base. Cependant, si le tableau est déjà trié ou trié approximativement, cette méthode de sélection peut faire dégénérer la complexité temporelle du tri rapide en O(n^2). Afin d'éviter cette situation, nous pouvons sélectionner aléatoirement un élément comme élément de référence, ce qui peut dans une certaine mesure rompre l'ordre des données d'entrée et améliorer les performances.

Ce qui suit est un exemple de code pour sélectionner aléatoirement l'élément de base :

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

    public static int randomPartition(int[] arr, int low, int high) {
        int randomIndex = ThreadLocalRandom.current().nextInt(low, high + 1);
        swap(arr, randomIndex, high);
        return partition(arr, low, high);
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 9, 1, 3, 7, 6};
        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }
}

2. Partitionnement à trois échantillonnages
   Dans l'algorithme de tri rapide traditionnel, un seul élément de base est utilisé pour diviser le tableau. Cependant, lorsqu'il y a un grand nombre d'éléments en double dans le tableau, une telle division entraînera une dégradation de la complexité temporelle du tri rapide à O(n^2). Afin de résoudre ce problème, nous pouvons utiliser la méthode de partitionnement médian sur trois pour être plus flexible dans la sélection des éléments de référence.

L'idée de base de la division en trois échantillonnages est de sélectionner trois éléments dans le tableau (tels que le premier, le dernier et le milieu), puis d'utiliser leur médiane comme élément de base. En utilisant une telle méthode de partitionnement, nous pouvons essayer d’éviter le problème de dégradation des performances lié au tri rapide lorsqu’il s’agit d’un grand nombre d’éléments répétés.

Ce qui suit est un exemple de code utilisant le partitionnement à trois échantillonnages :

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int[] pivotIndices = medianOfThree(arr, low, high);
            int left = pivotIndices[0];
            int right = pivotIndices[1];
            quickSort(arr, low, left - 1);
            quickSort(arr, left + 1, right - 1);
            quickSort(arr, right + 1, high);
        }
    }

    public static int[] medianOfThree(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (arr[high] < arr[low]) {
            swap(arr, low, high);
        }
        if (arr[mid] < arr[low]) {
            swap(arr, low, mid);
        }
        if (arr[high] < arr[mid]) {
            swap(arr, mid, high);
        }
        swap(arr, mid, high - 1);
        return partition(arr, low + 1, high - 1);
    }

    public static int[] partition(int[] arr, int low, int high) {
        int left = low;
        int right = high;
        int pivot = arr[high];
        int i = low - 1;
        while (true) {
            while (arr[++i] < pivot) {
            }
            while (left < right && pivot < arr[--right]) {
            }
            if (left >= right) {
                break;
            }
            swap(arr, left, right);
        }
        swap(arr, left, high);
        return new int[]{left, right};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 9, 1, 3, 7, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

En sélectionnant aléatoirement les éléments de base et en utilisant la méthode de partitionnement à trois échantillonnages, nous pouvons optimiser les performances de la fonction de tri rapide Java. Ces méthodes peuvent améliorer l’efficacité des algorithmes de tri lorsqu’il s’agit de différentes distributions de données et éviter la dégradation de la complexité temporelle.

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!