Exemples de code sur les bulles et le tri rapide

Cet article présente principalement le tri à bulles Java et un exemple de code de tri rapide. Les amis qui en ont besoin peuvent se référer au

tri à bulles

Le tri à bulles est un algorithme de tri simple. Il parcourt à plusieurs reprises la séquence à trier, en comparant deux éléments à la fois et en les échangeant s'ils sont dans le mauvais ordre. Le travail de visite du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié. Le nom de cet algorithme vient du fait que les éléments plus petits « flotteront » lentement vers le haut du tableau grâce à l’échange.

L'algorithme de tri des bulles est implémenté comme suit : [Après le tri, le tableau est disposé du petit au grand]

　　/**
  * 冒泡排序
  * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
  * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
  * 针对所有的元素重复以上的步骤，除了最后一个。
  * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 
  * @param numbers 需要排序的整型数组
  */
 public static void bubbleSort(int[] numbers)
 {
  int temp = 0;
  int size = numbers.length;
  for(int i = 0 ; i < size-1; i ++)
  {
  for(int j = 0 ;j < size-1-i ; j++)
  {
   if(numbers[j] > numbers[j+1]) //交换两数位置
   {
   temp = numbers[j];
   numbers[j] = numbers[j+1];
   numbers[j+1] = temp;
   }
  }
  }
 }

Tri rapide

L'idée de base du tri rapide :

Divisez les enregistrements à trier en deux parties indépendantes via une seule passe de tri, les mots-clés d'une partie des enregistrements sont plus petits que les mots-clés de l'autre partie, alors les deux parties continueront à être triées jusqu'à ce que toute la séquence soit en ordre.

Traitez la séquence entière comme un tableau, considérez la position zéro comme l'axe central et comparez-la avec la dernière si elle est plus petite que celle-ci, échangez-la, et si elle est plus grande, aucun traitement ne le fera. être fait ; après l'échange, il sera combiné avec le plus petit. Par rapport à cette extrémité, s'il est plus petit que lui, n'échangez pas, mais s'il est plus grand que lui, échangez-le. De cette façon, boucle d'avant en arrière, et le tri s'effectue en un seul passage. Celui de gauche est plus petit que l'axe central, et celui de droite est plus grand que l'axe central. Ensuite, diviser pour mieux régner. La méthode est utilisée pour trier les deux tableaux indépendants.

Le code est implémenté comme suit :

1. Trouver la position de l'axe central (le bit le plus bas est utilisé comme axe central)

　　/**
  * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
  * 
  * @param numbers 带查找数组
  * @param low 开始位置
  * @param high 结束位置
  * @return 中轴所在位置
  */
 public static int getMiddle(int[] numbers, int low,int high)
 {
  int temp = numbers[low]; //数组的第一个作为中轴
  while(low < high)
  {
  while(low < high && numbers[high] > temp)
  {
   high--;
  }
  numbers[low] = numbers[high];//比中轴小的记录移到低端
  while(low < high && numbers[low] < temp)
  {
   low++;
  }
  numbers[high] = numbers[low] ; //比中轴大的记录移到高端
  }
  numbers[low] = temp ; //中轴记录到尾
  return low ; // 返回中轴的位置
 }

2. Forme récursive d'algorithme de tri diviser pour régner :

 /**
  * 
  * @param numbers 带排序数组
  * @param low 开始位置
  * @param high 结束位置
  */
 public static void quickSort(int[] numbers,int low,int high)
 {
  if(low < high)
  {
  　　int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
  　　quickSort(numbers, low, middle-1); //对低字段表进行递归排序
  　　quickSort(numbers, middle+1, high); //对高字段表进行递归排序
  }
 }

3. appels

 /**
  * 快速排序
  * @param numbers 带排序数组
  */
 public static void quick(int[] numbers)
 {
  if(numbers.length > 0) //查看数组是否为空
  {
  quickSort(numbers, 0, numbers.length-1);
  }
 }

Analyse :

Le tri rapide est généralement considéré comme ayant la meilleure performance moyenne parmi les méthodes de tri du même ordre de grandeur (O( nlog2n)). Mais si la séquence initiale est ordonnée par clé ou fondamentalement ordonnée, le tri rapide dégénérera en tri à bulles. Afin de l'améliorer, la « méthode trois en un » est généralement utilisée pour sélectionner l'enregistrement de référence, c'est-à-dire que les trois clés d'enregistrement centrées sur les deux extrémités et le point médian de l'intervalle de tri sont ajustées en tant qu'enregistrement de point d'appui. Le tri rapide est une méthode de tri instable.

Test de méthode

ImpressionFonction :

public static void printArr(int[] numbers)
 {
  for(int i = 0 ; i < numbers.length ; i ++ )
  {
  System.out.print(numbers[i] + ",");
  }
  System.out.println("");
 }

Test :

　public static void main(String[] args) 
 {
  int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
  System.out.print("排序前：");
  printArr(numbers);
  bubbleSort(numbers);
  System.out.print("冒泡排序后：");
  printArr(numbers);
  quick(numbers);
  System.out.print("快速排序后：");
  printArr(numbers);
 }

Résultat :

Avant tri : 10,20,15,0,6,7,2,1, -5,55,

Après tri à bulles : -5,0,1,2,6,7,10,15,20,55,

Après tri rapide : -5, 0 ,1,2,6,7,10,15,20,55,

【Recommandations associées】

1 Recommandation spéciale : Téléchargez la version V0.1 de "php Programmer Toolbox"

2.Tutoriel vidéo gratuit Java

3 Analyse complète des annotations Java.

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!