public class QuickSort { public static void qkSort2(int[] nums, int left, int right) { if (left >= right) { return; } //选取 int base = nums[left]; int i = left, j = right; while (i < j) { //找到小于 base 的数 while (nums[j] >= base && i < j) { j--; } //找到大于 base 的数 while (nums[i] <= base && i < j) { i++; } //交换 swap(nums, i, j); } //交换基数和最终 i swap(nums,i, left); qkSort2(nums, left, i - 1); qkSort2(nums, i + 1, right); } public static void qkSort(int[] nums, int left, int right) { if (left >= right) { return; } //选取 int base = nums[left]; int i = left, j = right; while (i < j) { //找到小于 base 的数 while (nums[j] >= base && i < j) { j--; } //填坑 if (i<j){ nums[i++] = nums[j]; } //找到大于 base 的数 while (nums[i] <= base && i < j) { i++; } //填坑 if (i<j){ nums[j--]=nums[i]; } } //用基数填到最终的i的位置 nums[i] = base; qkSort(nums, left, i - 1); qkSort(nums, i + 1, right); } private static void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } public static void main(String[] args) { int[] num = {72,6,57,88,60,42,83,73,48}; qkSort(num, 0, num.length-1); System.out.println(Arrays.toString(num)); int[] num2 = {72,6,57,88,60,42,83,73,48}; qkSort2(num2, 0, num.length-1); System.out.println(Arrays.toString(num2)); } }
运行结果:
[6, 42, 48, 57, 60, 72, 73, 83, 88] [6, 42, 48, 57, 60, 72, 73, 83, 88] Process finished with exit code 0