[GO] Tri rapide

J'ai écrit un programme QuickSort. Il est pratique d'utiliser la récurrence.

Le tri rapide est

1. Sélectionnez Pivot dans la colonne de données
2. Divisez en pivot plus grand et plus petit
3. Alignez chaque divisé Je vais le trier comme ça.

Si Pivot est situé au centre de la chaîne de données, il s'agit de l'algorithme le moins intensif en calcul du tri et ne nécessite que O (nlogn). Si Pivot arrive à la toute fin, il faudra O (n ^ 2).

QuickSort.java

import java.util.*;
public class QuickSort {
    public static boolean debug = false;
    private static int partition(int[] a,int l,int r){
	if(debug)System.out.print("partition l="+l+", r="+r);
	int pivot = a[r];
	int i = l;
	int j = r-1;
	for (;;) {
	    while (a[i] < pivot) ++i;
	    while (i<j && a[j] >= pivot) --j;
	    if(debug) System.out.println("check i="+i+" ,j="+j+" ,pivot="+pivot);
	    if(i>=j) break;
	    if(debug) System.out.println("change i="+i+" ,j="+j);
	    int tmp = a[i];
	    a[i] = a[j];
	    a[j] = tmp;
	}
	int tmp = a[i];
	a[i] = a[r];
	a[r] = tmp;
	return i;
    }
    private static void quickSort(int[] a,int l,int r){
	if(l >= r) return;
	int v = partition(a,l,r);
	if(debug) System.out.println("l="+l+", r="+r+", v"+v+": "+toString(a));
	quickSort(a,l,v-1);
	quickSort(a,v+1,r);
    }
    public static void sort(int[] a){
	quickSort(a,0,a.length-1);
    }
    public static String toString(int[] a){
	StringBuffer sb = new StringBuffer();
	for (int i = 0; i < a.length; i++) sb.append(a[i]+" ");
	return sb.toString();
    }
    public static void main(String[] args) {
	if(args.length > 0 && args[0].equals("-d")) debug = true;
	Scanner sc = new Scanner(System.in);
	System.out.print("Veuillez saisir le nombre de données");
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) a[i] = sc.nextInt();
	sort(a);
	System.out.println(toString(a));
    }
}