Exemples de méthodes de tri en Java

Tri à bulles

Caractéristiques : faible efficacité, mise en œuvre simple

Idées (de petite à grande) : chacune Déplacer le le plus grand élément de la séquence à trier jusqu'à la fin, et le reste est la nouvelle séquence à trier. Répétez les étapes ci-dessus jusqu'à ce que tous les éléments soient triés. Il s'agit simplement d'un type de tri des bulles, bien sûr, il peut également être trié de l'arrière vers l'avant.

public void bubbleSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = 0; j < array.length - 1 - i; j++)                
        if (array[j] > array[j + 1]) {
                    t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                }
    }

Tri par sélection

Caractéristiques : faible efficacité, facile à mettre en œuvre

Idée : sélectionner le plus petit de la séquence à trier à chaque passage, les éléments sont placés à la fin de la séquence triée et les bits restants doivent être triés. Répétez les étapes ci-dessus jusqu'à ce que le tri soit terminé.

public void selectSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = i + 1; j < array.length; j++)                
        if (array[i] > array[j]) {
                    t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
    }

Tri par insertion

Caractéristiques : faible efficacité, facile à mettre en œuvre

Idée : diviser le tableau en deux parties et diviser cette dernière une partie des éléments Comparez-le avec les éléments précédents un par un. Si le tableau d'éléments actuel[i] est petit, remplacez-le. Trouvez une position raisonnable et insérez un tableau[i]

public void insertionSort(int array[]) {
        int i, j, t = 0;        
        for (i = 1; i < array.length; i++) {
            t = array[i];            
            for (j = i - 1; j >= 0 && t < array[j]; j--)
                array[j + 1] = array[j];
            array[j + 1] = t;
        }
    }

tri rapide

Caractéristiques : efficace, la complexité temporelle est inlogn.

Adoptez l'idée de​​la méthode diviser pour mieux régner : définissez d'abord un pivot de valeur d'axe, puis utilisez cette valeur d'axe comme base de division pour diviser la séquence à trier en deux parties plus grandes que la pivot et plus petit que le pivot, puis divisez les subdivisions en deux parties. La séquence est triée jusqu'à ce que la sous-séquence contienne un élément.

public void quickSort(int array[], int low, int high) {// 传入low=0，high=array.length-1;
        int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。        
        if (low < high) {
            p_pos = low;
            pivot = array[p_pos];            
            for (i = low + 1; i <= high; i++)                
            if (array[i] > pivot) {
                    p_pos++;
                    t = array[p_pos];
                    array[p_pos] = array[i];
                    array[i] = t;
                }
            t = array[low];
            array[low] = array[p_pos];
            array[p_pos] = t;            // 分而治之
            quickSort(array, low, p_pos - 1);// 排序左半部分
            quickSort(array, p_pos + 1, high);// 排序右半部分
        }

Tutoriel recommandé : Tutoriel Java

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!