Exemple simple de tri rapide en Java

Cet article présente principalement en détail des exemples de tri rapide simple Java, qui ont une certaine valeur de référence. Les amis intéressés peuvent s'y référer

1 Concepts de base

Trouver. un élément (en théorie, vous pouvez en trouver n'importe lequel) comme pivot (pivot), puis partitionner le tableau de sorte que la valeur de l'élément sur le côté gauche du pivot ne soit pas supérieure à la valeur du pivot, et la valeur de l'élément sur le côté droit du pivot n'est pas inférieur à La valeur de base, de sorte que l'élément utilisé comme base soit ajusté à la position correcte après le tri. Le tri rapide récursif ajuste les n-1 autres éléments à la position correcte après le tri. Enfin, chaque élément est dans la bonne position après le tri, et le tri est terminé. Par conséquent, l'algorithme de base de l'algorithme de tri rapide est l'opération de partition, c'est-à-dire comment ajuster la position du benchmark et ajuster la position finale du benchmark renvoyé pour la récursion diviser pour régner.

2. Sélectionnez l'élément de référence

1. Correction de l'élément de référence

Si la séquence d'entrée est aléatoire, le temps de traitement est acceptable. Si le tableau est déjà trié, la division à ce moment est une très mauvaise division. Étant donné que chaque division ne peut réduire la séquence à trier que d'une unité, il s'agit du pire des cas. Le tri rapide devient un tri à bulles et la complexité temporelle est Θ (n ^ 2). De plus, il est assez courant que les données d’entrée soient ordonnées ou partiellement ordonnées. Par conséquent, utiliser le premier élément comme élément de base est très mauvais et doit être abandonné immédiatement.

2. Élément de base aléatoire

Il s'agit d'une stratégie relativement sûre. La position de l'élément de référence étant aléatoire, la segmentation résultante ne sera pas toujours une segmentation de mauvaise qualité. Lorsque tous les numéros du tableau sont égaux, c'est toujours le pire des cas et la complexité temporelle est O(n^2). En fait, la probabilité de trier rapidement de manière aléatoire pour obtenir le pire des cas théoriques n'est que de 1/(2^n). Par conséquent, le tri rapide randomisé peut atteindre la complexité temporelle attendue de O(n×log(n)) pour la plupart des données d'entrée.

3. Trouver le milieu de trois nombres

La meilleure division est de diviser la séquence à trier en sous-séquences de longueur égale. Dans le meilleur état, on peut utiliser la valeur médiane du. séquence, c’est-à-dire le N/2ème nombre. Cependant, cela est difficile à calculer et ralentira considérablement le tri rapide. Une telle estimation de la médiane peut être obtenue en sélectionnant aléatoirement trois éléments et en utilisant leur médiane comme élément de base. En fait, le caractère aléatoire n'aide pas beaucoup, donc l'approche générale consiste à utiliser la médiane des trois éléments à l'extrémité gauche, à l'extrémité droite et au centre comme élément de base.

3. Algorithme de partition

L'algorithme de partition est au cœur du tri rapide. Avant d'apprendre le tri rapide, vous pouvez d'abord apprendre cet algorithme. Collez d'abord le code :

  public int partition(int[] num,int left,int right){
    if(num==null || num.length<=0 || left<0 || right>=num.length){
      return 0;
    }
    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标
    while (left<=right){         //从两端交替向中间扫描
      while (num[left]<prio)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最终将基准数归位 
        left++;
        right--;
      }
    }
    return left;
  }

L'idée de cette méthode est de trouver d'abord un élément pivot (le premier élément se retrouve dans la mise en œuvre de cette méthode, il y a en fait beaucoup de détails) L'article simplifiera la description ici), puis générera deux pointeurs gauche et droit des deux côtés du tableau (l'endroit spécifique où est déterminé par les paramètres transmis à chaque fois que l'on constate que). l'élément de gauche est plus grand que l'élément pivot, je s'arrêtera, et celui de droite le fera. Si l'élément est plus petit que l'élément pivot j, il s'arrête et les positions des deux nombres sont échangées. Jusqu'à ce que les deux pointeurs gauche et droit se rencontrent. Insérez ensuite l'élément pivot dans la position gauche, là où il devrait être.

Le résultat final est de faire apparaître la partie [gauche, droite] du tableau en deux parties. La position finale de l'élément pivot à gauche est inférieure ou égale à l'élément pivot, et la position finale à droite est supérieure ou égale à l'élément pivot. L'élément pivotant est inséré dans une position absolument correcte.

4. Implémentation de l'algorithme de tri

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一个数组中取一个基准数字，把小的数放基准的左边，大的数放基准的右边。
 * 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字，小的放左边，大的放右边。
 * 这个里面用到的递归。我们需要三个参数，一个是数组，另外两个是序列的边界
 * @author HJS
 */
public class QuickSort{

  void sort(int num[],int left,int right){
    if (left
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!