[JAVA] Die Idee der schnellen Sortierung

Am Anfang

Da die Implementierung der im Internet erläuterten schnellen Sortierung nicht gut war, werde ich einen Artikel hochladen, den ich selbst zusammengefasst habe. Die Richtlinie des Algorithmus übernimmt die Zerlegung und Neuaggregation von Elementen, die häufig in der Erklärung der Funktionssprache verwendet wird, und ich werde versuchen, sie in Java zu implementieren und zu sehen, wie mühsam die Implementierung der schnellen Sortierung in der Unterrichtssprache ist.

Die Idee der schnellen Sortierung

Betrachten Sie als Beispiel das Sortieren einer Reihe von Zahlen [6,1,8,5,9]. Wenn wir schnell sortieren, benötigen wir ein Kriterium, um die Elemente zu teilen, aber hier verwenden wir das erste Element der Menge für dieses Kriterium.

Zerlegtes Bild der Liste

Bild der aggregierten Liste nach der Zerlegung

Implementierungscode

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){
			//Wenn das Array ein Element enthält, beenden Sie die rekursive Verarbeitung
			return new ArrayList<Integer>(list) ;
		}else{
			//Rufen Sie den Prozess auf, um die Elemente in der Liste zu teilen
			Divive div = splitList(list);
			//Generieren Sie eine Liste zum Speichern des geteilten Arrays
			List<Integer>newList = new ArrayList<Integer>();
			//Führen Sie eine rekursive Verarbeitung durch, um einen kleinen Satz von Zahlen erneut zu trennen
			newList.addAll(qsort(div.leftList));
			//Führen Sie eine rekursive Verarbeitung durch, um einen großen Satz erneut zu isolieren
			newList.addAll(qsort(div.rightList));
			return newList ;
		}
	}

	//Funktion zum Teilen der Liste
	public static Divive splitList(List<Integer>list){
		int size =list.size();
		Divive div = new Divive();
		//Wenn die Anzahl der Elemente zwei beträgt, wird die Größe der Elemente verglichen und die Elemente werden geteilt.
		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>();
		//Teilen Sie die durch das Argument gegebene Liste nach einem vorgegebenen Kriterium in eine kleine Menge und eine große Menge.
		for(int i=0;i<size;i++){
			//Generieren Sie eine Reihe von Zahlen, die kleiner als die Referenz sind
			if(pivot>=list.get(i))smallIntList.add(list.get(i));
			//Generieren Sie eine Reihe von Zahlen, die größer als die Referenz sind
			if(pivot<list.get(size - 1- i))largeIntList.add(list.get(size - 1- i));
		}
		
		//Wenn die Argumente der von der kleinen Menge angegebenen Liste nicht übereinstimmen, geben Sie die geteilte Listenkombination an den Aufrufer zurück.
		if(smallIntList.size()!=list.size()){
			div.leftList.addAll(smallIntList);
			div.rightList.addAll(largeIntList);
		}
		//Wenn das Argument der durch das Argument angegebenen Liste mit der kleinen Menge übereinstimmt, ist die Referenznummer die kleinste
		//Teilen Sie die Liste ganz links in der Liste und an anderer Stelle
		else{
			Deque<Integer> que  = new ArrayDeque<Integer>(smallIntList);
			div.leftList.add(que.pop()) ;
			div.rightList.addAll(new ArrayList<Integer>(que))  ;
		}
		return div;
	}
	
	//Java kann keinen Binärwert für den Rückgabewert festlegen, daher muss eine Datenstruktur definiert werden, die die Menge nach der Division darstellt.
	static public class Divive{
		List<Integer>leftList =new ArrayList<Integer>();
		List<Integer>rightList =new ArrayList<Integer>();
	}
}