出处：算法第四版
public class QuickSort { public static void quickSort(int[] a) { helper(a, 0, a.length - 1); } private static void helper(int[] a, int lo, int hi) { if (hi <= lo) { return; } // 这一步中，选取切分元素，再根据切分元素调整整个数组 int j = partition(a, lo, hi); // 每次调整后打印下整个数组 for (int num : a) { System.out.print(num + " "); } // finish print System.out.println(); // 返回排序后的切分元素，再以切分元素分开左右两边分别排序 helper(a, lo, j - 1); helper(a, j + 1, hi); } private static int partition(int[] a, int lo, int hi) { int i = lo; int j = hi + 1; // 选择切分元素 int value = a[lo]; while (true) { // 从左到右找到第一个小于切分元素的元素index后停止 while (a[++i] < value) { if (i == hi) { break; } } // 从右到左找到第一个大于切分元素的元素index后停止 while (value < a[--j]) { if (j == lo) { break; } } // 被注释的写法冗余 // 从左到右找到第一个小于切分元素的元素index后停止// while (a[i] < value && i < a.length) {// i++;// if (i == hi) {// break;// }// }// // 从右到左找到第一个大于切分元素的元素index后停止// while (value < a[j] && j >= 0) {// j--;// if (j == lo) {// break;// }// } if (i >= j) { break; } exch(a, i, j); } // 将处于lo处的切分元素换到正确的位置j处 exch(a, lo, j); // 返回切分元素的正确位置 return j; } private static void exch(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[]{5, 3, 7, 3, 4, 8, 9, 43, 32, 56, 0}; quickSort(a); }}