java实现
public class QuickSort {
public static void quickSort(int[] a, int low, int high) {
if (high <= low)
return;
int j = partition(a, low, high); // 切分
quickSort(a, low, j-1); // 递归
quickSort(a, j+1, high); // 递归
}
// 切分
public static int partition(int[] a, int low, int high) {
int i = low; // 左扫描指针
int j = high+1; // 右扫描指针
int v = a[low]; // 切分元素
while (true) {
// 扫描左右，检查扫描是否结束并交换元素
// 当i和j相遇时主循环退出
while (a[++i] < v) {
if (i == high)
break;
}
while (v < a[--j]) {
if (j == low)
break;
}
if (i >= j)
break;
// 交换a[i]和a[j]来保证左侧元素都不大于v，右侧元素都不小于v
swap(a, i, j);
}
// 将v = a[j]放入正确的位置
swap(a, low, j);
return j;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int[] a = new int[] {2, 4, 7, 5, 11, 3, 1, 9, 7, 8, 10, 6, -1, 0};
quickSort(a, 0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
