Introduction détaillée au tri à bulles Java (exemple de code)

Le contenu de cet article est une introduction détaillée (exemple de code) sur le tri des bulles Java. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. aidé.

1. Introduction

Parce qu'il s'agit du premier article de la série sur les algorithmes de tri, je dirai quelques mots supplémentaires.

Le tri est l'un des algorithmes les plus courants. Désormais, de nombreux langages de programmation ont intégré certains algorithmes de tri, comme la méthode Arrays.sort() de Java. Cette méthode nous permet de l'appeler directement sans nous soucier de l'interne. détails de mise en œuvre. Il est également souvent utilisé dans le développement de logiciels réels. Mais du point de vue d'un développeur, pour savoir ce qui se passe, il faut savoir pourquoi. Pratiquer davantage d'algorithmes de tri nous permettra non seulement de connaître les détails sous-jacents de la mise en œuvre de certaines méthodes de tri, mais également d'exercer notre réflexion et d'améliorer nos capacités de programmation. De nombreux entretiens techniques impliquent désormais également des algorithmes de tri de base, il est donc avantageux de s'entraîner davantage. (Recommandé : Tutoriel vidéo Java)

Le code impliqué dans l'article est entièrement implémenté en Java, mais il n'impliquera pas trop de fonctionnalités du langage Java, et j'ajouterai des commentaires détaillés, aidant vous comprenez le code et le convertissez dans un langage de programmation que vous connaissez.

Il existe 10 algorithmes de tri courants :

• Tri à bulles, tri par sélection, tri par insertion, la complexité temporelle moyenne est O(n² )
• Tri par colline, tri par fusion, tri rapide, tri par tas, la complexité temporelle moyenne est O(nlogn)
• Tri par comptage, tri par base, tri par seau, la complexité temporelle moyenne est O(nlogn) C'est O(n + k)

Avant de commencer à expliquer l'algorithme de tri spécifique, vous devez d'abord comprendre deux concepts :

1. Tri sur place : fait référence au tri Le processus n'occupe pas d'espace de stockage supplémentaire et la complexité spatiale est O(1).
2. Stabilité de l'algorithme de tri : Un tri stable signifie qu'après le tri, l'ordre des mêmes éléments ne sera pas modifié. Sinon, il est dit instable. Par exemple : un tableau [3, 5, 1, 4, 9, 6, 6, 12] a deux 6 (pour distinction, j'ai mis un des 6 en gras), si après tri c'est comme ça : [1, 3, 4, 5, 6, 6, 9, 12] (le 6 en gras est toujours devant), ce qui montre qu'il s'agit d'un algorithme de tri stable.

2. Plus près de chez nous

L'idée du tri à bulles est en fait très simple. La taille d'une donnée est comparée à ses données adjacentes. Si la relation de taille est satisfaite, échangez les positions de ces deux données. En répétant cette opération, les données peuvent être triées.

Par exemple, s'il existe un tableau a[3,5,1,4,9,6], la première opération de bullage est la suivante :

Répétez cette opération. Après 6 bulles, le tri des données est terminé.

Selon cette idée, il devrait être facile d'écrire le code suivant pour implémenter le tri à bulles :

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

Mais cet algorithme de tri peut également être optimisé lorsque l'opération de bulle n'a pas de données. Lors de l'échange, cela signifie que le tri est terminé et qu'il n'est pas nécessaire d'effectuer des opérations de bullage. Par exemple, dans l'exemple ci-dessus, après la première bulle, les données sont [3,1,4,5,6,9], et après une autre bulle, les données deviennent [1,3,4,5,6,9 ] , le tri est terminé à ce moment et la boucle peut être terminée.

Donc, pour trier ce tableau, le code ci-dessus nécessite 6 bulles, dont 4 inutiles. Le code peut donc être optimisé :

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

D'accord, les idées de base et le code du tri à bulles ont été implémentés. Enfin, pour résumer :

1. Le tri à bulles est basé sur des données. La complexité temporelle dans le meilleur des cas de
2. est O(n), la complexité temporelle dans le pire des cas est O(n²) et la complexité temporelle moyenne est O(n ²)
3. Le tri à bulles est un algorithme de tri sur place et est stable.

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!