[GO] Schnelle Sorte

Ich habe ein QuickSort-Programm geschrieben. Es ist bequem, die Wiederholung zu verwenden.

Schnelle Sortierung ist

1. Wählen Sie Pivot aus der Datenspalte
2. Teilen Sie in größere und kleinere Pivot
3. Richten Sie jede geteilte aus Ich werde es so sortieren.

Befindet sich Pivot in der Mitte der Datenzeichenfolge, ist dies der am wenigsten rechenintensive Algorithmus in der Sortierung und erfordert nur O (nlogn). Wenn Pivot ganz am Ende ist, wird O (n ^ 2) benötigt.

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("Bitte geben Sie die Anzahl der Daten ein");
	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));
    }
}