Maison  >  Article  >  Java  >  Implémentation Java d'un exemple de tri rapide QuickSort

Implémentation Java d'un exemple de tri rapide QuickSort

黄舟
黄舟original
2017-10-09 09:53:111908parcourir

L'éditeur suivant vous apportera un tri rapide Java QuickSort (exemple). L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Venez jeter un œil avec la rédaction

Tri rapide

---------------- -------------------------------------------------- ----

Pensées

Comme indiqué ci-dessus : au début de chaque tri rapide, définissez une clé, clé = array[low], puis allez de haut en gauche, trouvez la valeur plus petite que la clé, copiez-la en position basse, puis allez de bas en droite pour trouver la valeur supérieure à la clé, copiez-la en position haute , jusqu'à ce que bas = haut se termine,

La clé est copiée en position basse.

Après le premier tour de division dans la figure ci-dessus, la position de 32 est trouvée, puis les côtés gauche et droit de 32 sont triés de manière récursive.

Code :


package Sort;
import java.util.Arrays;
public class QuickSort {

 public static void main(String[] args) {
  int array[]={32, 12, 7, 78, 23, 45};
  quickSort(array,0,array.length-1);
  System.out.println(Arrays.toString(array));
 }
 public static void quickSort(int array[],int left,int right)
 {
  if(left>=right)
  {
   return ;
  }
  int i=left;
  int j=right;
  int key=array[left];
  while(i<j)
  {
   while(i<j&&array[j]>key)
   {
    j--;
   }
   array[i]=array[j];
   //从后往前找到第一个比key小的数与array[i]交换;
   while(i<j&&array[i]<key)
   {
    i++;
   }
   array[j]=array[i];
   //从前往后找到第一个比key大的数与array[j]交换;
  }
  array[i]=key;
  //一趟快排之后已经将key的位置找到。
  quickSort(array,left,i-1);
  //对key左边的进行排序
  quickSort(array,i+1,right);
  //对key右边的进行排序
 }
}

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn