So sortieren Sie mithilfe der Schnellsortierung in der Sprache C

So ordnen Sie die Schnellsortiermethode an: Legen Sie zunächst bei jeder Sortierung einen Referenzpunkt fest und platzieren Sie alle Zahlen, die kleiner oder gleich dem Referenzpunkt sind, links vom Referenzpunkt gleich dem Referenzpunkt rechts vom Referenzpunkt; Schließlich wird jeder Austausch nicht wie eine Blasensortierung sein, die jedes Mal nur zwischen benachbarten Zahlen ausgetauscht werden kann, und der Austauschabstand wird viel größer sein.

Sortiermethode der Schnellsortierung:

Algorithmusidee:

(1) Wir wählen einen Datensatz (normalerweise den ersten) aus der zu sortierenden Datensatzfolge als Basiselement (Schlüssel genannt) aus )key=arr[left] und legen Sie dann zwei Variablen fest: Left zeigt auf den Teil ganz links im Array und Right zeigt auf den Teil ganz rechts der Daten.

(2) Key wird zuerst mit arr[right]key, dann müssen wir nur right--, right-- vergleichen und dann arr[right] mit key vergleichen, bis arr[right]

(3) Wenn arr[right]key, dann arr[right]=arr[left], wenn arr[left]

(4) Bewegen Sie sich dann nach rechts und wiederholen Sie die obigen Schritte.

(5) Erhalten Sie schließlich {23 58 13 10 57 62} 65 {106 78 95 85} und vergleichen Sie dann das linke Unterarray und rechtes Unterarray Machen Sie dasselbe. Schließlich wird eine geordnete Sequenz erhalten.

Algorithmusimplementierung:

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));
   }
}

排序前：[65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85]
排序后：[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]

Verwandte Lernempfehlungen: C-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo sortieren Sie mithilfe der Schnellsortierung in der Sprache C. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!