[JAVA] L'idée du tri rapide

Au début

Puisque la mise en œuvre du tri rapide expliquée sur le net ne s'est pas bien déroulée, je vais mettre en ligne un article que j'ai moi-même résumé. La politique de l'algorithme adopte la décomposition et la réagrégation d'éléments, ce qui est souvent repris dans l'explication des langages fonctionnels, et je vais essayer de l'implémenter en Java et voir à quel point il est difficile d'implémenter le tri rapide dans les langages d'enseignement.

L'idée du tri rapide

À titre d'exemple, envisagez de trier un ensemble de nombres [6,1,8,5,9]. Lors d'un tri rapide, nous avons besoin d'un critère pour diviser les éléments, mais ici nous utiliserons le premier élément de l'ensemble pour ce critère.

Image démontée de la liste

Image de liste agrégée après décomposition

Code d'implémentation

Qsort.java

package test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class QSort {

	public static void main(String args[]){
		System.out.println(qsort(Arrays.asList(1,5,6,2,11,9,4)));
	}

	public static List<Integer> qsort(List<Integer>list){
		if(list.size()==1){
			//Si le tableau contient un élément, quittez le traitement récursif
			return new ArrayList<Integer>(list) ;
		}else{
			//Appelez le processus pour diviser les éléments dans la liste
			Divive div = splitList(list);
			//Générer une liste pour stocker le tableau fractionné
			List<Integer>newList = new ArrayList<Integer>();
			//Effectuer un traitement récursif pour séparer à nouveau un petit ensemble de nombres
			newList.addAll(qsort(div.leftList));
			//Effectuer un traitement récursif pour isoler à nouveau un grand ensemble
			newList.addAll(qsort(div.rightList));
			return newList ;
		}
	}

	//Fonction pour diviser la liste
	public static Divive splitList(List<Integer>list){
		int size =list.size();
		Divive div = new Divive();
		//Lorsque le nombre d'éléments est de deux, la taille des éléments est comparée et les éléments sont divisés.
		if(size==2){
			if(list.get(0)<=list.get(1)){
				div.leftList.add(list.get(0))  ;
				div.rightList.add(list.get(1))  ;
			}else{
				div.leftList.add(list.get(1))  ;
				div.rightList.add(list.get(0))  ;
			}
			return div;
		}

		int pivot = list.get(0);
		List<Integer>smallIntList =new ArrayList<Integer>();
		List<Integer>largeIntList =new ArrayList<Integer>();
		//Divisez la liste donnée par l'argument en un petit ensemble et un grand ensemble selon un critère prédéterminé.
		for(int i=0;i<size;i++){
			//Générer un ensemble de nombres plus petits que la référence
			if(pivot>=list.get(i))smallIntList.add(list.get(i));
			//Générer un ensemble de nombres plus grands que la référence
			if(pivot<list.get(size - 1- i))largeIntList.add(list.get(size - 1- i));
		}
		
		//Si les arguments de la liste donnée par le petit ensemble ne correspondent pas, renvoyez la combinaison de listes fractionnées à l'appelant.
		if(smallIntList.size()!=list.size()){
			div.leftList.addAll(smallIntList);
			div.rightList.addAll(largeIntList);
		}
		//Si l'argument de la liste donnée par l'argument correspond au petit ensemble, le numéro de référence est le plus petit, donc
		//Divisez la liste à l'extrême gauche de la liste et ailleurs
		else{
			Deque<Integer> que  = new ArrayDeque<Integer>(smallIntList);
			div.leftList.add(que.pop()) ;
			div.rightList.addAll(new ArrayList<Integer>(que))  ;
		}
		return div;
	}
	
	//Java ne peut pas définir une valeur binaire pour la valeur de retour, il est donc nécessaire de définir une structure de données qui représente l'ensemble après la division.
	static public class Divive{
		List<Integer>leftList =new ArrayList<Integer>();
		List<Integer>rightList =new ArrayList<Integer>();
	}
}