Schnelle Sortierung in Java

Prinzip der Schnellsortierung

Die Schnellsortierung ist eine Verbesserung der Blasensortierung, bei der eins nach dem anderen verglichen wird, wodurch kleine Werte an einem Ende platziert werden Am anderen Ende wird ein größerer Wert platziert, um den Zweck der Sortierung zu erreichen.

Schnelles Sortieren besteht darin, zunächst einen kritischen Wert auszuwählen, die Werte, die kleiner als der kritische Wert sind, an einem Ende anzubringen und die Werte, die größer als der kritische Wert sind am anderen Ende. Wiederholen Sie die Methode im vorherigen Absatz, und Sie können die beiden Seiten, die den kritischen Wert überschritten haben, teilen und zweimal teilen ... Nach dem Sortieren der Daten ist die gesamte Schnellsortierung abgeschlossen.

Schnellsortieralgorithmus

Kernalgorithmus:

//QuickSort
while(i < j) {
		while(num[j] > tmp && j > i)
			--j;
		while(num[i] <= tmp && i < j) {
			++i;
		}
		if(i < j) {
			t = num[i];
			num[i] = num[j];
			num[j] = t;
		}
	}
	num[left] = num[i];
	num[i] = tmp;

Das Folgende ist das vollständige QuickSort-Programm:

//QuickSort.java
public class QuickSort {
	public static void main(String[] args) {
		int[] num = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		System.out.print("Qriginal array is:");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
		
		//QuickSort
		quicksort(num, 0, 9);
		
		System.out.print("Sorted array is:");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
	}
	
	public static void quicksort(int[] num, int left, int right) {
		if(left > right)
			return;
		int tmp, i, j, t;
		tmp = num[left];
		i = left;
		j = right;
		while(i < j) {
			while(num[j] > tmp && j > i)
				--j;
			while(num[i] <= tmp && i < j) {
				++i;
			}
			if(i < j) {
				t = num[i];
				num[i] = num[j];
				num[j] = t;
			}
		}
		num[left] = num[i];
		num[i] = tmp;
		quicksort(num, left, i - 1);
		quicksort(num, i + 1, right);
	}
}

Die Programmausgabe sieht wie folgt aus:

Qriginal array is:10 9 8 7 6 5 4 3 2 1
Sorted array is:1 2 3 4 5 6 7 8 9 10

Schnellsortierung ist effizienter als andere Sortiermethoden, daher ist Schnellsortierung derzeit die beste allgemeine Sortiermethode. Die Zeitkomplexität von QuickSort beträgt O(nlogn).

Das obige ist der detaillierte Inhalt vonSchnelle Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!