Tri rapide en Java

Principe du tri rapide

Le tri rapide est une amélioration du tri à bulles compare une par une, plaçant ainsi de petites valeurs à une extrémité et la. une valeur plus grande est placée à l'autre extrémité pour atteindre l'objectif de tri.

Le tri rapide consiste à sélectionner d'abord une valeur critique, à mettre les valeurs plus petites que la valeur critique à une extrémité et à mettre les valeurs plus grandes que la valeur critique à l'autre bout. En répétant la méthode du paragraphe précédent, vous pouvez diviser les deux côtés qui ont dépassé la valeur critique et les diviser deux fois... Après le tri des données, l'ensemble du tri rapide est terminé.

Algorithme de tri rapide

Algorithme de base :

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

Ce qui suit est le programme complet de tri rapide :

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

Le résultat du programme est le suivant :

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

Le tri rapide est plus efficace que les autres méthodes de tri, le tri rapide est donc la meilleure méthode de tri générale actuellement. La complexité temporelle de QuickSort est O(nlogn).

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!