Comment maîtriser rapidement les algorithmes de recherche et les algorithmes de tri en programmation Java

1. Algorithme de recherche

Algorithme binaire

La recherche binaire, également connue sous le nom de demi-recherche, est un algorithme de recherche efficace. Son idée de base est la suivante : divisez le tableau ordonné (ou l'ensemble) en deux. Si l'élément central actuel est égal à l'élément cible, la recherche est réussie. Si l'élément central actuel est supérieur à l'élément cible, la moitié gauche est recherchée. ; si l'élément central actuel est inférieur à Pour l'élément cible, recherchez la moitié droite. Répétez les étapes ci-dessus jusqu'à ce que l'élément cible soit trouvé ou que la plage de recherche soit vide et que la recherche échoue.

Ce qui suit est un algorithme binaire implémenté en Java :

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

La méthode ci-dessus utilise un ensemble de tableaux d'entiers ordonnés et une valeur cible comme paramètres, et renvoie la valeur cible dans le tableau L'index ; si la valeur cible n'existe pas dans le tableau, il renvoie -1.

Le cœur de l'algorithme est la boucle while, qui est exécutée à plusieurs reprises lorsque la gauche et la droite remplissent des conditions spécifiques :

• If mid est égal pour cibler, Puis revenez mid et l'algorithme se termine ;

• Si mid est supérieur à la cible, continuez la recherche à gauche, c'est-à-dire réglez à droite sur mid - 1 ;

  #🎜🎜 #
• Si le milieu est plus petit que la cible, continuez la recherche sur la droite, c'est-à-dire réglez la gauche sur le milieu + 1.

À chaque fois dans la boucle, nous utilisons mid = left + (right - left) / 2 pour calculer l'index de l'élément du milieu. Il est à noter qu'il faut utiliser la forme gauche + droite et non la forme (gauche + droite) / 2, sinon cela risque de provoquer des problèmes de débordement d'entier.

2. Algorithme de tri

En Java, l'algorithme de tri est implémenté en implémentant l'interface Comparable ou Comparator. Voici plusieurs algorithmes de tri couramment utilisés et leurs méthodes de mise en œuvre :

Tri à bulles

Le tri à bulles est un algorithme de tri simple. L'idée est de comparer constamment deux éléments adjacents, et si l'ordre est erroné, d'échanger leurs positions. Ce processus est comme si des bulles d’eau montaient continuellement, c’est ce qu’on appelle le tri des bulles.

public static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                //交换位置
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Tri par sélection

L'idée du tri par sélection est de sélectionner le plus petit élément parmi les éléments non triés et de le mettre à la fin du tri. Chaque fois que le plus petit élément est trouvé, il est remplacé par le premier élément actuellement non trié.

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Tri par insertion

L'idée du tri par insertion est d'insérer des éléments non triés dans la position triée appropriée. Sélectionnez un élément parmi les éléments non triés et parcourez les éléments triés d'arrière en avant. S'il est plus petit que l'élément trié, déplacez-le d'une position vers l'arrière et continuez la comparaison jusqu'à ce que vous trouviez une position plus petite que l'élément non trié, puis insérez-le à l'emplacement souhaité. cet endroit.

public static void insertionSort(int[] arr) {
    int preIndex, current;
    for (int i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

Quick Sort

Le tri rapide est un algorithme de tri basé sur l'idée de diviser pour régner. Il sélectionne un point pivot, divise le tableau en deux sous-tableaux inférieurs ou égaux au point pivot et supérieurs au point pivot, puis trie de manière récursive les deux sous-tableaux.

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

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!