Comment trier en utilisant le tri rapide en langage C

Méthode de tri rapide : Tout d'abord, définissez un point de référence à chaque fois que vous triez, et placez tous les nombres inférieurs ou égaux au point de référence à gauche du point de référence ; égale au point de référence. A droite du point de référence ; enfin, chaque échange ne sera pas comme un tri à bulles où seuls les numéros adjacents pourront être échangés à chaque fois, et la distance d'échange sera beaucoup plus grande.

Arrangement de tri rapide :

Idée algorithmique :

( 1) Nous sélectionnons un enregistrement (généralement le premier) de la séquence d'enregistrements à trier comme élément de référence (appelé clé) key=arr[left], puis définissons deux variables, gauche pointe vers la partie la plus à gauche de la séquence, droite pointe vers la partie la plus à droite des données.

(2) la clé est d'abord comparée à arr[right], si arr[right]key, alors il suffit de comparer right--, right--, puis de comparer arr[right] avec key jusqu'à arr[right]

(3) Si arr[right]key, alors arr[right]=arr[left]. Si arr[left]

(4) Ensuite, déplacez-vous vers la droite et répétez les étapes ci-dessus

(5) Obtenez enfin {23 58 13 10 57 62} 65 {106 78 95 85}, puis effectuez la même opération sur le sous-réseau gauche et le sous-réseau droit. Finalement, une séquence ordonnée est obtenue.

Implémentation de l'algorithme :

public class QuickSort {
 
   public static void quickSort(int [] arr,int left,int right) {
      int pivot=0;
      if(left<right) {
         pivot=partition(arr,left,right);
         quickSort(arr,left,pivot-1);
         quickSort(arr,pivot+1,right);
      }
   }
 
   private static int partition(int[] arr,int left,int right) {
      int key=arr[left];
      while(left<right) {
         while(left<right && arr[right]>=key) {
            right--;
         }
         arr[left]=arr[right];
         while(left<right && arr[left]<=key) {
            left++;
         }
         arr[right]=arr[left];
      }
      arr[left]=key;
      return left;
   }
  
   public static void main(String[] args) {
      int arr[]= {65,58,95,10,57,62,13,106,78,23,85};
      System.out.println("排序前："+Arrays.toString(arr));
      quickSort(arr,0,arr.length-1);
      System.out.println("排序后："+Arrays.toString(arr));
   }
}

rrree

Recommandations d'apprentissage associées : Tutoriel vidéo C

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!