快排算法的基本原理
1、从数据中选取一个值a[i]作为参考
2、以a[i] 为参考,将数据分成2部分:P1、P2,P1中的数据全部≤a[i],P2中的数据全部>a[i],数据变为{{P1}{a[i]}{P2}}
3、将P1、P2重复上述步骤,直到各部分中只剩1个数据
4、数据完成升序排列
public class QuickSort {
private void sort(int[] data, int left, int right) {
int i = left;
int j = right;
int middle = data[(left + right) / 2];
do {
while (data[i] < middle && i < right) {
i++;
}
while (data[j] > middle && j > left) {
j--;
}
if (i <= j) {
int itemp = data[i];
data[i] = data[j];
data[j] = itemp;
i++;
j--;
}
} while (i <= j);
if (left < j) {
sort(data, left, j);
}
if (right > i) {
sort(data, i, right);
}
}
public void sort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void main(String[] args) {
QuickSort sort = new QuickSort();
int[] data = {3, 1, 5, 8, 9, 2, 6, 4, 0, 10, 3};
sort.sort(data);
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}