Comment implémenter l'algorithme de tri par base en utilisant Java

Comment implémenter un algorithme de tri par base en utilisant Java ?

L'algorithme de tri par base est un algorithme de tri non comparatif qui trie en fonction de la valeur binaire des éléments. Son idée principale est de regrouper les nombres à trier selon les unités, dizaines, centaines et autres chiffres, puis de trier chaque chiffre tour à tour pour finalement obtenir une séquence ordonnée. Ce qui suit présentera en détail comment implémenter l'algorithme de tri par base à l'aide de Java et fournira des exemples de code.

Tout d'abord, l'algorithme de tri par base doit préparer un tableau bidimensionnel pour enregistrer les nombres à trier. Le nombre de lignes du tableau est déterminé par le nombre de chiffres. Par exemple, si le nombre maximum de nombres à trier est n, alors le nombre de lignes du tableau est log(n) + 1. Chaque colonne est utilisée pour stocker le numéro correspondant à ce chiffre.

Ensuite, vous devez trouver la valeur maximale parmi les nombres à trier pour déterminer le nombre de chiffres dans la base. Ceci peut être réalisé en parcourant l'ensemble du tableau et en prenant la valeur maximale.

Ensuite, commencez le tri par base. Tout d’abord, répartissez les numéros dans les compartiments correspondants en fonction d’un seul chiffre. Vous pouvez utiliser le tri par comptage pour réaliser cette étape. La méthode spécifique consiste à créer un tableau de comptage d'une taille de 10, à parcourir les nombres du tableau à trier, à placer les nombres dans les compartiments correspondants en fonction de chiffres simples, puis à trier les nombres dans les compartiments. Après le tri, remettez les nombres dans le compartiment dans le tableau pour les trier dans l'ordre.

Ensuite, attribuez à nouveau les nombres aux compartiments correspondants en fonction du chiffre des dizaines et triez les nombres dans les compartiments. Après le tri, remettez les nombres dans le compartiment dans le tableau pour les trier à nouveau dans l'ordre.

Répétez les étapes ci-dessus jusqu'à ce que tous les chiffres soient attribués et triés. Enfin, les nombres du tableau à trier sont ordonnés.

Ce qui suit est un exemple de code d'utilisation de Java pour implémenter le tri par base :

public class RadixSort {
    public static void radixSort(int[] arr) {
        // 找到待排序数组中的最大值，确定需要进行排序的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
      
        // 计算需要进行排序的位数
        int digit = 1;
        while (max / 10 > 0) {
            max /= 10;
            digit++;
        }
      
        // 创建桶和计数数组
        int[][] bucket = new int[10][arr.length];
        int[] count = new int[10];
      
        // 进行基数排序
        for (int i = 0; i < digit; i++) {
            for (int j = 0; j < arr.length; j++) {
                int num = (arr[j] / (int) Math.pow(10, i)) % 10;
                bucket[num][count[num]++] = arr[j];
            }
          
            int k = 0;
            for (int j = 0; j < count.length; j++) {
                if (count[j] != 0) {
                    for (int l = 0; l < count[j]; l++) {
                        arr[k++] = bucket[j][l];
                    }
                    count[j] = 0;
                }
            }
        }
    }
  
    public static void main(String[] args) {
        int[] arr = {432, 524, 236, 679, 321, 546, 457};
        radixSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Ce qui précède est la méthode et l'exemple de code d'utilisation de Java pour implémenter l'algorithme de tri par base. Il convient de noter que l'algorithme de tri par base convient au tri d'entiers positifs. Pour les entiers négatifs ou les tableaux contenant des nombres négatifs, ils doivent d'abord être convertis en nombres non négatifs pour le 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!