Comment implémenter un algorithme de tri par comptage à l'aide de Java

Comment implémenter un algorithme de tri par comptage en Java

Le tri par comptage est un algorithme de tri sans comparaison. Son idée principale est de compter le nombre de fois où chaque élément apparaît dans le tableau, puis de placer l'élément dans la bonne position. en fonction du nombre de fois où il apparaît. La complexité temporelle du tri par comptage est O(n+k), où n est la longueur de la séquence à trier et k est la plage du plus grand élément de la séquence à trier.

En Java, nous pouvons utiliser l'exemple de code suivant pour implémenter l'algorithme de tri par comptage :

public class CountingSort {
    public static void countingSort(int[] array) {
        int n = array.length;
        
        // 找到待排序序列中的最大值
        int max = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 创建一个计数数组，并初始化为0
        int[] count = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            count[i] = 0;
        }
        
        // 统计每个元素在待排序序列中出现的次数
        for (int i = 0; i < n; i++) {
            count[array[i]]++;
        }
        
        // 根据计数数组构建有序序列
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                array[index] = i;
                index++;
                count[i]--;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] array = {9, 1, 5, 3, 7, 3, 8, 2, 6};
        
        System.out.println("排序前：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        countingSort(array);
        
        System.out.println("排序后：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Dans le code ci-dessus, nous trouvons d'abord la valeur maximale dans la séquence à trier, puis créons un tableau de comptage et ajoutons le nombre d'occurrences de chaque élément Les statistiques sont dans le tableau count. Ensuite, nous construisons une séquence ordonnée basée sur le tableau de comptage. L'opération spécifique consiste à placer les éléments du tableau de comptage dans la séquence à trier en fonction du nombre d'occurrences. Enfin, en appelant la méthode countingSort et en imprimant la séquence ordonnée, nous pouvons voir les résultats du tri par comptage.

Il convient de noter que le tri par comptage a certaines restrictions sur la plage d'éléments de la séquence à trier et n'est applicable qu'aux séquences entières non négatives. S'il y a des nombres négatifs ou des éléments d'autres types de données dans la séquence à trier, un traitement approprié est requis avant que l'algorithme de tri par comptage puisse être utilisé.

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!