算法导论·快排

QuickSort.java

public class QuickSort {

  public static int partition(int[] nums, int p, int r) {
		int x = nums[r];// 取最后一位作为基准
		int i = p - 1;

		for (int j = p; j < r; j++) {
			if (nums[j] <= x) {
				i++;
				// 交换
				int a = nums[i];
				nums[i] = nums[j];
				nums[j] = a;
			}
			for (int m = p; m <= r; m++) {
				System.out.print(nums[m] + " ");
			}
			System.out.println();
		}

		int a = nums[i + 1];
		nums[i + 1] = nums[r];
		nums[r] = a;
		for (int m = p; m <= r; m++) {
			System.out.print(nums[m] + " ");
		}
		System.out.println();
		System.out.println("i =" + i);
		return i;
	}

	public static void quick_sort(int[] nums, int p, int r) {
		if (p < r) {
			int q = partition(nums, p, r);
			quick_sort(nums, p, q);
			quick_sort(nums, q + 1, r);
		}
	}

	public static void main(String[] args) {

	  int[] readInts = { 5, 2, 1, 4, 6, 3 };
		quick_sort(readInts, 0, readInts.length - 1);
		for (int i = 0; i < readInts.length; i++) {
			System.out.print(readInts[i] + " ");
		}
		System.out.println("done");
	}

}