Skip to content

Instantly share code, notes, and snippets.

@dodola
Created September 3, 2013 06:19
Show Gist options
  • Save dodola/6420258 to your computer and use it in GitHub Desktop.
Save dodola/6420258 to your computer and use it in GitHub Desktop.
算法导论·快排
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");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment