Principe de l'algorithme de tri rapide et implémentation récursive Java

Le tri rapide est une amélioration du tri à bulles. Si la séquence d'enregistrement initiale est triée par mot-clé ou fondamentalement ordonnée, elle dégénère en tri à bulles. Il utilise le principe récursif et présente les meilleures performances moyennes parmi toutes les méthodes de tri du même ordre de grandeur O(n longn). En termes de temps moyen, elle est actuellement considérée comme la meilleure méthode de tri interne

L'idée de base est la suivante : diviser les données à trier en deux parties indépendantes grâce à un tri unidirectionnel, et toutes les données d'une partie sont plus petit que Toutes les données de l'autre partie doivent être petites, puis utilisez cette méthode pour trier rapidement les deux parties des données respectivement. L'ensemble du processus de tri peut être effectué de manière récursive, de sorte que les données entières deviennent une séquence ordonnée.

Trois pointeurs : le premier pointeur est appelé le pointeur pivot (pivot), le deuxième pointeur et le troisième pointeur sont respectivement le pointeur gauche et le pointeur droit, pointant respectivement vers la valeur la plus à gauche et la valeur la plus à droite. . Le pointeur gauche et le pointeur droit s'approchent des deux côtés vers le milieu en même temps. Pendant l'approche, ils sont constamment comparés au pivot, déplaçant les éléments plus petits que le pivot vers l'extrémité inférieure et les éléments mobiles plus grands que le pivot vers. le haut de gamme Une fois sélectionné, il ne changera jamais, se retrouvant au milieu, plus petit devant et plus grand derrière.

Nécessite deux fonctions :

① Fonction récursive public static void quickSort(int[]n ,int left,int right)
② Fonction Split (fonction de tri rapide en un seul passage) public partition int statique (int[]n,int left,int right)

Code source JAVA (exécuté avec succès) :

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

Plus d'articles liés aux principes de l'algorithme de tri rapide et à l'implémentation récursive de Java Veuillez faire attention au site Web PHP chinois !