Analyse détaillée étape par étape de la mise en œuvre d'un algorithme de tri rapide en Java

Analyse détaillée étape par étape de l'implémentation Java de l'algorithme de tri rapide

Quick Sort est un algorithme de tri efficace qui utilise l'idée de diviser pour régner en divisant la séquence à trier en sous-séquences plus petites, puis trier les sous-séquences et enfin fusionner les sous-séquences pour obtenir une séquence ordonnée. Cet article présentera en détail les étapes de l'algorithme de tri rapide et fournira des exemples de code Java spécifiques.

1. Étapes de l'algorithme :

Les étapes de base de l'algorithme de tri rapide sont les suivantes :

1.1 Sélectionnez un élément comme pivot (pivot), qui peut être le premier élément, le dernier élément ou un élément sélectionné au hasard.

1.2 Divisez la séquence à trier en deux sous-séquences : une séquence d'éléments inférieure ou égale au benchmark et une séquence d'éléments supérieure au benchmark.

1.3 Appliquer de manière récursive l'algorithme de tri rapide à deux sous-séquences.

1.4 Fusionner les sous-séquences pour obtenir une séquence ordonnée complète.

2. Exemple de code Java :

Ce qui suit est un exemple de code spécifique utilisant Java pour implémenter l'algorithme de tri rapide :

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0 || low >= high) {
            return;
        }

        // 选择基准元素
        int pivotIndex = partition(arr, low, high);

        // 对基准元素左边的子序列递归排序
        quickSort(arr, low, pivotIndex - 1);

        // 对基准元素右边的子序列递归排序
        quickSort(arr, pivotIndex + 1, high);
    }

    private 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;
    }
    
    private 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, 2, 9, 1, 6, 3, 8, 4, 7};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("排序后的结果：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

3. Description de l'exemple :

Dans le code ci-dessus, nous définissons un quickSort méthode code> Utilisée pour trier la séquence à trier, la méthode <code>partition permet de diviser la séquence en deux sous-séquences. quickSort方法用于对待排序序列进行排序，partition方法用于将序列分割成两个子序列。

在quickSort方法中，首先判断序列是否需要排序，然后选择基准元素，并调用partition方法将序列分割。接着，对两个子序列递归应用quickSort方法，直到序列长度为1。

partition方法选择最后一个元素作为基准，并使用变量i记录小于等于基准的元素个数。通过遍历序列，如果元素小于等于基准，则将其与i

Dans la méthode quickSort, déterminez d'abord si la séquence doit être triée, puis sélectionnez l'élément de base et appelez la méthode partition pour diviser la séquence. Ensuite, appliquez la méthode quickSort de manière récursive aux deux sous-séquences jusqu'à ce que la longueur de la séquence soit 1.

La méthode partition sélectionne le dernier élément comme ligne de base et utilise la variable i pour enregistrer le nombre d'éléments inférieurs ou égaux à la ligne de base. En parcourant la séquence, si l'élément est inférieur ou égal à la référence, il est échangé avec la position pointée par i, et enfin l'élément de référence est placé à la position appropriée.

Enfin, exécutez la fonction principale pour afficher les résultats triés. 🎜🎜La complexité temporelle de l'algorithme de tri rapide est O(nlogn) et a une grande efficacité. En comprenant et en appliquant correctement les étapes ci-dessus, l'algorithme de tri rapide peut être appliqué de manière flexible dans la programmation réelle pour répondre aux exigences de tri. 🎜

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!