Exemple de code d'implémentation Java du tri par comptage (CountingSort)

Cet article vous apporte des exemples de code sur l'implémentation Java du tri par comptage (CountingSort). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Le tri par comptage est un type spécial de tri par seau.

Quand n données doivent être triées, si la plage n'est pas grande, on peut prendre la valeur maximale K et disperser les données dans K buckets,

chacun Les données dans les buckets sont toutes les mêmes (cela permet de gagner du temps de tri dans les seaux), puis ils sont sortis dans l'ordre.

Bien sûr, compter et trier, c'est simple à dire, mais il y a certaines choses qui sont difficiles à comprendre lors de l'écriture.

Par exemple, nous avons maintenant 8 nombres : 2, 5, 3, 0, 2, 3, 0, 3. Pour les trier, nous pouvons d'abord obtenir sa valeur maximale de 5, puis déterminer la plage .0-5,

On demande un espace mémoire de 0-5 pour calculer le numéro de chaque numéro correspondant à chaque position.

L'image ci-dessous montre les données dans l'espace mémoire 0-5. Nous pouvons voir que 0 apparaît deux fois, 1 apparaît 0 fois, 2 apparaît deux fois, 3 apparaît trois fois et 4 apparaît 0 fois. est apparu une fois.

En même temps, on peut aussi résumer certaines règles. Par exemple, on voit maintenant la position de c[2], 2 apparaître deux fois, et devant 2, c[0] +. c[1] a un total de 2 éléments, donc c[2] correspond aux positions de ces deux 2 dans le tableau d'origine, qui sont 2 et 3. On peut tracer la règle selon laquelle la position de c[2] = c [0] + c[1], et la position c[3 ] suivante = c[2] + c[1], nous les additionnons séquentiellement comme ceci : Ensuite, nous analysons le tableau d'origine 2, 5, 3, 0, 2, 3, 0, 3, chaque fois que nous rencontrons un nombre, substituons ce nombre dans l'index du tableau c pour obtenir l'index réel de l'élément courant après tri.

Mon implémentation Java est la suivante :

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 13:45
 **/
public class CountingSort {
    public static void main(String[] args) {
        int[] numbers = {3, 9, 2, 1, 8, 7, 6, 10, 9};
        // 假设数组中存储的都是非负整数
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 计数排序
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers){
        int n = numbers.length;
        int maxNumber = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        int[] r = new int[n];
        int[] c = new int[maxNumber + 1];
        for(int i = 0; i < n; ++i){
            c[numbers[i]]++;
        }
        for(int i = 1; i <= maxNumber; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
}

Le code clé :

for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;5         
            }

Récupérer l'index trié du tableau c.

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!