Comment implémenter un algorithme de tri rapide en utilisant Java

Comment implémenter un algorithme de tri rapide en Java

Quick Sort est un algorithme de tri couramment utilisé et efficace. Son idée de base est d'adopter la stratégie diviser pour régner (Divide and Conquer). En sélectionnant un élément à la fois comme valeur de référence, le tableau à trier est divisé en deux parties, une partie est plus petite que la valeur de référence et l'autre partie est plus grande que la valeur de référence, puis les deux parties sont divisées en deux parties. Effectuez un tri récursif partiel et réalisez enfin le tri de l'ensemble du tableau.

Ci-dessous, nous présenterons en détail comment implémenter l'algorithme de tri rapide à l'aide du langage Java et fournirons des exemples de code spécifiques.

1. Étapes de mise en œuvre de l'algorithme :

   • Choisissez une valeur de référence (peut être n'importe quel nombre, choisissez généralement le premier élément du tableau)
   • Divisez le tableau en deux parties, et les éléments dans la partie gauche sont tous plus petits) ; que la valeur de référence, les éléments dans la partie droite sont tous supérieurs à la valeur de référence ;
   • Triez rapidement les parties gauche et droite de manière récursive ;
2. Exemple de code Java :

public class QuickSort {
    
    public static void main(String[] args) {
        int[] arr = {5, 7, 2, 9, 3, 6, 1, 8, 4};
        quickSort(arr, 0, arr.length - 1);
        printArray(arr);
    }
    
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);  // 将数组划分为两部分，获取基准值的位置
            quickSort(arr, low, pivotIndex - 1);  // 递归排序基准值左边的部分
            quickSort(arr, pivotIndex + 1, high);  // 递归排序基准值右边的部分
        }
    }
    
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];  // 选择数组的第一个元素作为基准值
        int left = low + 1;
        int right = high;
        
        while (true) {
            while (left <= right && arr[left] < pivot) {  // 从左往右找到第一个大于或等于基准值的元素
                left++;
            }
            while (left <= right && arr[right] > pivot) {  // 从右往左找到第一个小于或等于基准值的元素
                right--;
            }
            if (left > right) {
                break;  // 左右指针相遇时退出循环
            }
            swap(arr, left, right);  // 交换左右指针指向的元素
        }
        swap(arr, low, right);  // 将基准值放回正确的位置
        return 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 printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

3. Analyse des performances :

   • Complexité temporelle : la complexité temporelle moyenne du tri rapide est O(nlogn), dans le pire des cas, elle est O(n^2), et dans le pire des cas, c'est O(n^2). Dans de bonnes circonstances, c'est O(n)
   • Complexité spatiale : la complexité spatiale du tri rapide est O(logn), en raison de l'espace de pile des appels récursifs.

Grâce à l'introduction ci-dessus, nous avons appris à utiliser le langage Java pour implémenter l'algorithme de tri rapide et compris ses idées de base, ses étapes et son analyse des performances. Le tri rapide est un algorithme de tri couramment utilisé qui peut trier efficacement tout type de données et est particulièrement adapté au tri de données à grande échelle.

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!