package com.eshore.sweetop.sort;
import java.util.Arrays;
public class Quick {
private static int partition(int[] a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (a[j] < x) {
i++;
if (i != j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
}
}
if (i + 1 != r) {
a[i + 1] ^= a[r];
a[r] ^= a[i + 1];
a[i + 1] ^= a[r];
}
return i + 1;
}
public static void sort2(int[] a, int p, int r) {
if (p < r) {
int q = partition(a, p, r);
sort2(a, p, q - 1);
sort2(a, q + 1, r);
}
}
public static void sort(int[] a) {
sort2(a, 0, a.length - 1);
}
public static void main(String[] args) {
int[] a = { 3, 4, 11, 13, 6, 8, 9, 2, 6 };
sort(a);
System.out.println(Arrays.toString(a));
}
}
