Java implémente un algorithme de tri rapide (Quicktsort)

Introduction à l'algorithme de tri rapide
Le tri rapide et le tri par fusion utilisent tous deux la méthode diviser pour régner pour concevoir des algorithmes. La différence est que le tri par fusion divise le tableau en deux sous-tableaux de longueurs fondamentalement égales. , ils doivent être fusionnés. (Fusionner), et le tri rapide est plus artistique lors de la division de sous-tableaux. Après la division, les éléments à gauche de l'élément de référence sont plus petits que l'élément de référence. ceux de droite ne sont pas plus petits que l'élément de référence. De cette façon, il vous suffit de trier simplement les deux sous-tableaux et de ne plus nécessiter une opération de fusion comme le tri par fusion. La sélection des éléments de référence a un grand impact sur l'efficacité de l'algorithme. Le meilleur des cas est que les deux sous-tableaux ont fondamentalement la même taille. Pour plus de simplicité, nous sélectionnons le dernier élément. Une approche plus avancée peut d'abord trouver une médiane et échanger la médiane avec le dernier élément, puis effectuer les mêmes étapes. Le fractionnement est au cœur du tri rapide. La durée d'exécution dans le pire des cas du tri rapide est O(n2), mais la durée d'exécution attendue est O(nlgn).

Implémentation Java d'un algorithme de tri rapide
1. Divisez le tableau en deux sous-tableaux plus un élément de base : sélectionnez le dernier élément comme élément de base et la variable d'index enregistre l'emplacement du plus récent. élément plus petit que l'élément de base. La position est initialisée à start-1. Si un nouvel élément est plus petit que l'élément de base, l'index est augmenté de 1. Du premier élément à l'avant-dernier élément, il est comparé à l'élément de base en séquence. S'il est inférieur à l'élément de base, l'indice est augmenté de 1 et l'indice de position et l'élément à la position actuelle sont échangés. Une fois la boucle terminée, l'index 1 obtient la position où doit se trouver l'élément de base et échange l'index 1 et le dernier élément.
2. Triez respectivement les deux sous-tableaux [start, index] et [index 2, end]
Comme dans "Implémentation Java d'Insertsort", implémentez d'abord une classe d'outils de tableau. Le code est le suivant :

public class ArrayUtils {

     public static void printArray(int[] array) {
      System.out.print("{");
      for (int i = 0; i < array.length; i++) {
       System.out.print(array[i]);
       if (i < array.length - 1) {
        System.out.print(", ");
       }
      }
      System.out.println("}");
     }
     public static void exchangeElements(int[] array, int index1, int index2) {
      int temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
     }
    }

L'implémentation Java et le code de test du tri rapide sont les suivants :

public class QuickSort {

  public static void main(String[] args) {
   int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
   System.out.println("Before sort:");
   ArrayUtils.printArray(array);
   quickSort(array);
   System.out.println("After sort:");
   ArrayUtils.printArray(array);
  }
  public static void quickSort(int[] array) {
   subQuickSort(array, 0, array.length - 1);
  }
  private static void subQuickSort(int[] array, int start, int end) {
   if (array == null || (end - start + 1) < 2) {
    return;
   }
   int part = partition(array, start, end);
   if (part == start) {
    subQuickSort(array, part + 1, end);
   } else if (part == end) {
    subQuickSort(array, start, part - 1);
   } else {
    subQuickSort(array, start, part - 1);
    subQuickSort(array, part + 1, end);
   }
  }
  private static int partition(int[] array, int start, int end) {
   int value = array[end];
   int index = start - 1;
   for (int i = start; i < end; i++) {
    if (array[i] < value) {
     index++;
     if (index != i) {
      ArrayUtils.exchangeElements(array, index, i);
     }
    }
   }
   if ((index + 1) != end) {
    ArrayUtils.exchangeElements(array, index + 1, end);
   }
   return index + 1;
  }
 }

Pour plus d'articles liés à l'implémentation Java de l'algorithme de tri rapide (Quicktsort ), veuillez faire attention au site Web PHP chinois !