Maison Java javaDidacticiel Évaluation de l'efficacité et des performances de Java Quick Sort

Évaluation de l'efficacité et des performances de Java Quick Sort

Feb 19, 2024 pm 10:16 PM
性能 比较 快速排序 tri à bulles

Évaluation de lefficacité et des performances de Java Quick Sort

Analyse et comparaison des performances de Java Quick Sort

Quick Sort (Quick Sort) est un algorithme de tri basé sur la comparaison qui est largement utilisé dans le développement réel en raison de sa vitesse d'exécution rapide et de ses bonnes performances. Cet article effectuera une analyse des performances de l'algorithme de tri rapide en Java et le comparera avec d'autres algorithmes de tri courants.

  1. Principe de l'algorithme de tri rapide
    Le tri rapide adopte l'idée de​​la méthode diviser pour régner. En divisant les données à trier en deux parties indépendantes, les sous-séquences gauche et droite sont triées de manière récursive, de manière à obtenir un résultat. le but de commander la séquence entière. Les étapes spécifiques de l'algorithme sont les suivantes :
    1) Sélectionnez une valeur d'axe (Pivot) dans le tableau, généralement le premier élément du tableau.
    2) Divisez le tableau en sous-séquences gauche et droite en une seule passe de tri, de sorte que les éléments de la sous-séquence de gauche soient inférieurs ou égaux à la valeur de l'axe et que les éléments de la sous-séquence de droite soient supérieurs à la valeur de l'axe.
    3) Triez rapidement les sous-séquences gauche et droite de manière récursive jusqu'à ce que la longueur de la séquence soit 1 ou 0.
    4) Obtenez enfin la séquence triée.
  2. Implémentation du tri rapide en Java
    Ce qui suit est un exemple de code pour implémenter le tri rapide en Java :

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

public class QuickSort {

  public static void quickSort(int[] arr, int low, int high) {

    if (low < high) {

      int pivotIdx = partition(arr, low, high);

      quickSort(arr, low, pivotIdx - 1);

      quickSort(arr, pivotIdx + 1, high);

    }

  }

   

  private static int partition(int[] arr, int low, int high) {

    int pivot = arr[low];

    int i = low + 1;

    int j = high;

     

    while (i <= j) {

      if (arr[i] <= pivot) {

        i++;

      } else if (arr[j] > pivot) {

        j--;

      } else {

        swap(arr, i, j);

      }

    }

     

    swap(arr, low, j);

     

    return j;

  }

   

  private static void swap(int[] arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

  }

   

  public static void main(String[] args) {

    int[] arr = {5, 2, 9, 1, 3, 7};

    quickSort(arr, 0, arr.length - 1);

    System.out.println(Arrays.toString(arr));

  }

}

Copier après la connexion
  1. Analyse et comparaison des performances
    Pour évaluer les performances de l'algorithme de tri rapide, nous l'avons comparé à plusieurs autres algorithmes de tri courants. Comparer. Vous trouverez ci-dessous un exemple de code qui utilise la méthode System.nanoTime() de Java pour calculer le temps d'exécution d'un algorithme :

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

import java.util.Arrays;

 

public class SortComparison {

  public static void main(String[] args) {

    int[] arr = generateArray(10000);

     

    long startTime = System.nanoTime();

    bubbleSort(arr.clone());

    long endTime = System.nanoTime();

    System.out.println("Bubble Sort: " + (endTime - startTime) + " ns");

     

    startTime = System.nanoTime();

    insertionSort(arr.clone());

    endTime = System.nanoTime();

    System.out.println("Insertion Sort: " + (endTime - startTime) + " ns");

     

    startTime = System.nanoTime();

    selectionSort(arr.clone());

    endTime = System.nanoTime();

    System.out.println("Selection Sort: " + (endTime - startTime) + " ns");

     

    startTime = System.nanoTime();

    quickSort(arr.clone(), 0, arr.length - 1);

    endTime = System.nanoTime();

    System.out.println("Quick Sort: " + (endTime - startTime) + " ns");

  }

   

  private static int[] generateArray(int size) {

    int[] arr = new int[size];

    for (int i = 0; i < size; i++) {

      arr[i] = (int)(Math.random() * size);

    }

    return arr;

  }

   

  private static void bubbleSort(int[] arr) {

    // 省略冒泡排序的具体实现

  }

   

  private static void insertionSort(int[] arr) {

    // 省略插入排序的具体实现

  }

   

  private static void selectionSort(int[] arr) {

    // 省略选择排序的具体实现

  }

   

  private static void quickSort(int[] arr, int low, int high) {

    // 省略快速排序的具体实现

  }

}

Copier après la connexion

En exécutant le code ci-dessus, nous pouvons obtenir le temps d'exécution de chaque algorithme de tri. Selon les résultats expérimentaux, l’algorithme de tri rapide est généralement plus rapide que le tri à bulles, le tri par insertion et le tri par sélection, en particulier pour trier des ensembles de données à grande échelle. Bien entendu, dans certains cas spécifiques, les performances d'autres algorithmes de tri peuvent être meilleures, c'est pourquoi une analyse spécifique de problèmes spécifiques est effectuée et l'algorithme de tri le plus approprié est sélectionné en fonction de la situation réelle.

Résumé :
Cet article effectue une analyse des performances de l'algorithme de tri rapide en Java et le compare à d'autres algorithmes de tri courants. Grâce à des résultats expérimentaux, nous pouvons conclure que le tri rapide est généralement un algorithme de tri efficace, particulièrement adapté au tri d’ensembles de données à grande échelle. Cependant, pour des problèmes spécifiques, nous devons choisir l’algorithme de tri le plus approprié en fonction de la situation réelle.

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Comparaison des performances de différents frameworks Java Comparaison des performances de différents frameworks Java Jun 05, 2024 pm 07:14 PM

Comparaison des performances de différents frameworks Java : Traitement des requêtes API REST : Vert.x est le meilleur, avec un taux de requêtes de 2 fois SpringBoot et 3 fois Dropwizard. Requête de base de données : HibernateORM de SpringBoot est meilleur que l'ORM de Vert.x et Dropwizard. Opérations de mise en cache : le client Hazelcast de Vert.x est supérieur aux mécanismes de mise en cache de SpringBoot et Dropwizard. Cadre approprié : choisissez en fonction des exigences de l'application. Vert.x convient aux services Web hautes performances, SpringBoot convient aux applications gourmandes en données et Dropwizard convient à l'architecture de microservices.

Inversion des valeurs clés du tableau PHP : analyse comparative des performances de différentes méthodes Inversion des valeurs clés du tableau PHP : analyse comparative des performances de différentes méthodes May 03, 2024 pm 09:03 PM

La comparaison des performances des méthodes de retournement des valeurs de clé de tableau PHP montre que la fonction array_flip() fonctionne mieux que la boucle for dans les grands tableaux (plus d'un million d'éléments) et prend moins de temps. La méthode de la boucle for consistant à retourner manuellement les valeurs clés prend un temps relativement long.

Transformez le code avec des pointeurs de fonctions C++ : améliorez l'efficacité et la réutilisabilité Transformez le code avec des pointeurs de fonctions C++ : améliorez l'efficacité et la réutilisabilité Apr 29, 2024 pm 06:45 PM

La technologie des pointeurs de fonction peut améliorer l'efficacité et la réutilisabilité du code, en particulier comme suit : Efficacité améliorée : l'utilisation de pointeurs de fonction peut réduire la répétition du code et optimiser le processus d'appel. Améliorer la réutilisabilité : les pointeurs de fonction permettent d'utiliser des fonctions générales pour traiter différentes données, améliorant ainsi la réutilisabilité du programme.

Comment optimiser les performances des programmes multi-thread en C++ ? Comment optimiser les performances des programmes multi-thread en C++ ? Jun 05, 2024 pm 02:04 PM

Les techniques efficaces pour optimiser les performances multithread C++ incluent la limitation du nombre de threads pour éviter les conflits de ressources. Utilisez des verrous mutex légers pour réduire les conflits. Optimisez la portée du verrou et minimisez le temps d’attente. Utilisez des structures de données sans verrouillage pour améliorer la simultanéité. Évitez les attentes occupées et informez les threads de la disponibilité des ressources via des événements.

Structures de données et algorithmes Java : explication détaillée Structures de données et algorithmes Java : explication détaillée May 08, 2024 pm 10:12 PM

Les structures de données et les algorithmes sont à la base du développement Java. Cet article explore en profondeur les structures de données clés (telles que les tableaux, les listes chaînées, les arbres, etc.) et les algorithmes (tels que le tri, la recherche, les algorithmes graphiques, etc.) en Java. Ces structures sont illustrées par des exemples pratiques, notamment l'utilisation de tableaux pour stocker les scores, de listes chaînées pour gérer les listes de courses, de piles pour implémenter la récursion, de files d'attente pour synchroniser les threads, ainsi que d'arbres et de tables de hachage pour une recherche et une authentification rapides. Comprendre ces concepts vous permet d'écrire du code Java efficace et maintenable.

Guide pour écrire un algorithme de tri personnalisé pour les tableaux PHP Guide pour écrire un algorithme de tri personnalisé pour les tableaux PHP Apr 27, 2024 pm 06:12 PM

Comment écrire un algorithme de tri de tableau PHP personnalisé ? Tri à bulles : trie un tableau en comparant et en échangeant des éléments adjacents. Tri par sélection : sélectionnez à chaque fois l'élément le plus petit ou le plus grand et échangez-le avec la position actuelle. Tri par insertion : insérez les éléments dans une pièce ordonnée un par un.

Comment utiliser des benchmarks pour évaluer les performances des fonctions Java ? Comment utiliser des benchmarks pour évaluer les performances des fonctions Java ? Apr 19, 2024 pm 10:18 PM

Un moyen de comparer les performances des fonctions Java consiste à utiliser Java Microbenchmark Suite (JMH). Les étapes spécifiques incluent : Ajout de dépendances JMH au projet. Créez une nouvelle classe Java et annotez-la avec @State pour représenter la méthode de référence. Écrivez la méthode de benchmark dans la classe et annotez-la avec @Benchmark. Exécutez le test de performance à l'aide de l'outil de ligne de commande JMH.

Quel est l'impact sur les performances de la conversion de tableaux PHP en objets ? Quel est l'impact sur les performances de la conversion de tableaux PHP en objets ? Apr 30, 2024 am 08:39 AM

En PHP, la conversion de tableaux en objets aura un impact sur les performances, principalement affecté par des facteurs tels que la taille du tableau, la complexité, la classe d'objet, etc. Pour optimiser les performances, envisagez d'utiliser des itérateurs personnalisés, en évitant les conversions inutiles, les tableaux de conversion par lots et d'autres techniques.

See all articles