Prinzip des Schnellsortierungsalgorithmus und rekursive Java-Implementierung

Schnellsortierung ist eine Verbesserung gegenüber der Blasensortierung. Wenn die anfängliche Datensatzreihenfolge nach Schlüsselwörtern oder grundsätzlich geordnet ist, degeneriert sie zur Blasensortierung. Es verwendet das rekursive Prinzip und weist unter allen Sortiermethoden derselben Größenordnung O(n longn) die beste durchschnittliche Leistung auf. In Bezug auf die durchschnittliche Zeit gilt sie derzeit als die beste interne Sortiermethode

Die Grundidee besteht darin, die zu sortierenden Daten durch Einwegsortierung in zwei unabhängige Teile aufzuteilen und alle Daten in einem Teil zusammenzufassen kleiner als Alle Daten im anderen Teil müssen klein sein. Verwenden Sie dann diese Methode, um die beiden Teile der Daten schnell zu sortieren. Der gesamte Sortiervorgang kann rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz werden.

Drei Zeiger: Der erste Zeiger wird als Pivotkey-Zeiger (Pivot) bezeichnet, der zweite Zeiger und der dritte Zeiger sind der linke Zeiger bzw. der rechte Zeiger und zeigen auf den Wert ganz links bzw. den Wert ganz rechts . Der linke Zeiger und der rechte Zeiger nähern sich gleichzeitig von beiden Seiten der Mitte. Während der Annäherung werden sie ständig mit dem Drehpunkt verglichen, wobei sie Elemente, die kleiner als der Drehpunkt sind, zum unteren Ende bewegen und Elemente, die größer als der Drehpunkt sind, dorthin Das obere Ende wird sich nach der Auswahl nie ändern und landet in der Mitte, wobei die Vorderseite klein und die Rückseite groß ist.

Erfordert zwei Funktionen:

① Rekursive Funktion public static void quickSort(int[]n ,int left,int right)
② Split-Funktion (Schnellsortierungsfunktion in einem Durchgang) öffentlich static int partition(int[]n,int left,int right)

JAVA-Quellcode (erfolgreich ausgeführt):

package testSortAlgorithm;
public class QuickSort {
 public static void main(String[] args) {
  int [] array = {49,38,65,97,76,13,27};
  quickSort(array, 0, array.length - 1);
  for (int i = 0; i < array.length; i++) {
   System.out.println(array[i]);
  }
 }
 /*先按照数组为数据原型写出算法，再写出扩展性算法。数组{49,38,65,97,76,13,27}
  * */
 public static void quickSort(int[]n ,int left,int right){
  int pivot;
  if (left < right) {
   //pivot作为枢轴，较之小的元素在左，较之大的元素在右
   pivot = partition(n, left, right);
   //对左右数组递归调用快速排序，直到顺序完全正确
   quickSort(n, left, pivot - 1);
   quickSort(n, pivot + 1, right);
  }
 }

 public static int partition(int[]n ,int left,int right){
  int pivotkey = n[left];
  //枢轴选定后永远不变，最终在中间，前小后大
  while (left < right) {
   while (left < right && n[right] >= pivotkey) --right;
   //将比枢轴小的元素移到低端，此时right位相当于空，等待低位比pivotkey大的数补上
   n[left] = n[right];
   while (left < right && n[left] <= pivotkey) ++left;
   //将比枢轴大的元素移到高端，此时left位相当于空，等待高位比pivotkey小的数补上
   n[right] = n[left];
  }
  //当left == right，完成一趟快速排序，此时left位相当于空，等待pivotkey补上
  n[left] = pivotkey;
  return left;
 }
}

Weitere Artikel zu den Prinzipien des Schnellsortierungsalgorithmus und der rekursiven Java-Implementierung Bitte achten Sie auf die chinesische PHP-Website!