Introduction détaillée au tri des tableaux

Un aperçu

1. Boucle double couche

Trier Généralement implémenté par une boucle à double couche, la boucle externe contrôle le nombre de tours de boucle et la boucle interne implémente un tri unique. L'indice de la boucle externe va de 1 à arr.length-1, et le nombre d'itérations de la boucle interne diminue à mesure que le nombre d'itérations de la boucle externe augmente.

Deux méthodes de bouillonnement

1 Idée de base

Comparez adjacent Si le. deux éléments remplissent les conditions, ils échangeront leurs positions, de sorte que le plus grand élément sera déplacé vers l'arrière.

2. Implémentation de l'algorithme

public static int[] bubbleSort(int[] arr) {for (int i = 1; i < arr.length; i++) {for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }return arr;
    }

Trois tris directs

1. Idée de base

Filtrez la valeur maximale de la séquence non triée et placez-la à la fin de la séquence non triée. La boucle externe boucle une fois, échangeant la valeur maximale de la séquence non triée avec la position du dernier élément de la séquence non triée. Les positions des autres éléments restent inchangées. La clé est d'obtenir l'index de la valeur maximale. Le tri direct est plus rapide que le tri à bulles.

Point d'entrée de la boucle interne : supposons que le premier élément de la séquence non triée, c'est-à-dire l'élément d'index 0, est la valeur maximale, puis comparez-le avec les éléments restants pour obtenir l’indice de la valeur maximale.

2. Implémentation de l'algorithme

public static int[] directSort(int[] arr) {int len = arr.length;int index;for (int i = 1; i < len; i++) {
            index = 0;for (int j = 1; j <= len - i; j++) {if (arr[index] < arr[j]) {
                    index = j;
                }int temp = arr[len - i];
                arr[len - i] = arr[index];
                arr[index] = temp;
            }
        }return arr;
    }

Tri à quatre inversions

1. Idée de base

Pour échanger les positions de deux éléments dont la somme d'index est arr.length-1, une seule boucle est nécessaire et le nombre de boucles est arr. longueur/2- 1.

2. Mise en œuvre de l'algorithme

public static int[] reverseSort(int[] arr) {for (int i = 0; i < arr.length / 2; i++) {int temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }return arr;
    }

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!