So implementieren Sie eine schnelle Sortierung in Java

Im folgenden Abschnitt der Kolumne Java-Einführung wird erläutert, wie die schnelle Sortierung in Java implementiert wird. Ich hoffe, dass dieser Sortieralgorithmus allen helfen kann!

Die zeitliche Komplexität der Schnellsortierung ist nicht festgelegt. Im schlimmsten Fall (Auswahl des ersten Elements als Basiselement in einem ursprünglich umgekehrt sortierten Array) ist die Geschwindigkeit relativ langsam und erreicht O(n^2). ) (eine Effizienz ähnlich der Auswahlsortierung), aber wenn die Zeitkomplexität unter idealen Umständen O(nlogn) ist.

Der Schlüssel zur Implementierung einer schnellen Sortierung besteht darin, zuerst eine Zahl im Array auszuwählen und dann die Zahl im Array in zwei Teile zu teilen. Die Zahl, die kleiner als die ausgewählte Zahl ist, wird nach links verschoben im Array und ist kleiner als die ausgewählte Zahl. Die größere Zahl wird nach rechts vom Array verschoben. Dies verkörpert die Idee des Teilens und Herrschens.

Lassen Sie uns diese Funktion implementieren:

int Partition(int data[],int length,int start,int end)
{
	if(data == nullptr || length <= 0 || start < 0 || end >=length)
		throw new std::exception("Invalid Parameters");
	int index = RandomInRange(start,end);
	Swap(&data[index],&data[end]);
	int small = start - 1;
	for(index = start; index < end; index++)
	{
		if(data[index]<data[end])
		{
			++small;
			if(small != index)
				Swap(&data[index],&data[small]);
		}
	}
	++small;
	Swap(&data[small],&data[end]);
	return small;
}
int RandomInRange(int min, int max)
{
	int random = rand()%(max - min +1) +min;
	return random;
}
int Swap(int *num1, int *num2)
{
	int temp = *num1;
	*num1 = num2;
	*num2 = temp;
}

Die Funktion RandomInRange im obigen Code wird verwendet, um eine Zufallszahl zwischen Anfang und Ende zu generieren, und die Funktion Swap wird verwendet, um zwei Zahlen auszutauschen.

Im Folgenden verwenden wir Rekursion, um einen schnellen Sortiercode zu implementieren:

void QuickSort(int data[], int length, int start, int end)
{
	if(start == end)
		return;
	int index = Partition(data, length, start, end);
	if(index > start)
		QuickSort(data, length, start, index -1);
	if(index < end)
		QuickSort(data, length, index + 1, end);
}

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