Comment implémenter le tri rapide en Java

La section suivante de la colonne apprentissage d'introduction à Java présentera comment implémenter le tri rapide en Java. J'espère que cet algorithme de tri pourra aider tout le monde !

La complexité temporelle du tri rapide n'est pas corrigée. Si dans le pire des cas (sélection du premier élément comme élément de base dans un tableau initialement trié de manière inversée), la vitesse est relativement lente, atteignant O (n ^ 2). ) (une efficacité similaire au tri par sélection), mais si la complexité temporelle est O(nlogn) dans des circonstances idéales.

La clé pour mettre en œuvre un tri rapide est de sélectionner d'abord un nombre dans le tableau, puis de diviser le nombre dans le tableau en deux parties. Le nombre plus petit que le nombre sélectionné est déplacé vers la gauche de. le tableau et est plus petit que le nombre sélectionné. Le nombre le plus grand est déplacé vers la droite du tableau. Cela reflète l’idée de diviser pour régner.

Implémentons cette fonction :

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;
}

La fonction RandomInRange dans le code ci-dessus est utilisée pour générer un nombre aléatoire entre le début et la fin, et la fonction Swap est utilisée pour échanger deux nombres.

Ci-dessous, nous utilisons la récursion pour implémenter le code de tri rapide :

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);
}

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!