Algorithme de tri rapide implémenté en langage Java

Une méthode d'implémentation d'un algorithme de tri rapide basé sur le langage Java

Le tri rapide est un algorithme de tri efficace, qui est souvent utilisé pour trier de grandes quantités de données. Cet article présentera une méthode d'implémentation d'un algorithme de tri rapide basé sur le langage Java et fournira des exemples de code spécifiques.

L'idée de base du tri rapide est de diviser les données à trier en deux parties indépendantes. Par exemple, en utilisant un élément comme valeur standard, les éléments plus petits que la valeur sont placés à gauche et les éléments plus grands que la valeur. la valeur est placée à droite. Triez ensuite rapidement ces deux parties séparément jusqu'à ce que toute la séquence soit triée.

Tout d'abord, nous devons implémenter une fonction de partition pour diviser les données. Cette fonction divise toute la séquence en deux parties en sélectionnant un Pivot (généralement en sélectionnant le premier élément de la séquence) et renvoie la position du Pivot. Le code spécifique est le suivant :

public class QuickSort {
    public int partition(int[] array, int low, int high) {
        int pivot = array[low]; // 选择第一个元素作为Pivot
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            array[low] = array[high]; // 将小于Pivot的元素移到左边

            while (low < high && array[low] <= pivot) {
                low++;
            }
            array[high] = array[low]; // 将大于Pivot的元素移到右边
        }
        array[low] = pivot; // 将Pivot放到正确的位置
        return low; // 返回Pivot的位置
    }
}

Ensuite, nous devons implémenter la fonction QuickSort pour trier la séquence entière. Le code spécifique est le suivant :

public class QuickSort {
    // ... 上面的代码省略 ...

    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high); // 划分序列
            quickSort(array, low, pivotIndex - 1); // 对左边序列进行快速排序
            quickSort(array, pivotIndex + 1, high); // 对右边序列进行快速排序
        }
    }
}

Enfin, nous pouvons utiliser la classe QuickSort pour trier un tableau d'entiers. Le code spécifique est le suivant :

public class Main {
    public static void main(String[] args) {
        int[] array = {5, 2, 6, 3, 1, 4}; // 待排序的数组

        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(array, 0, array.length - 1); // 对数组进行快速排序

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

Ce qui précède est une méthode pour implémenter l'algorithme de tri rapide basé sur le langage Java. En implémentant la fonction Partition et la fonction QuickSort, nous pouvons trier rapidement un tableau d'entiers. Cet algorithme a une complexité temporelle de O(nlogn) et constitue un algorithme de tri très efficace.

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!