[JAVA] 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));
    }
}

Recommended Posts

Tri rapide
Tri rapide | Commande la plus importante
tri rapide en python
Les débutants en Python organisent des tri rapides
Tri rapide sans utiliser le tri
Tri rapide 2 | Facile avec la notation d'inclusion de liste