快速排序的基本思路是,每次选定数列中的一个基准数,将小于基准数的数字都放到基准数左边,大于基准数的数字都放到基准数右边。然后再分别对基准数左右的两个数列分别重复以上过程。仍以4 3 6 2 7 1 5为例。
选定最左侧数字4为基准数,首先从右开始向左找小于4的数,找到第一个数1后停止。然后从左开始向右找到第一个大于4的数,即6。交换这两个数的位置,得到
继续寻找,仍然从右边开始,从上一步找到1的位置向左寻找小于4的数,找到2停止。然后从左边找到6的位置向右找大于4的数。右移一格后,和右侧来的“探路者”相遇了,这意味着这一轮排序结束。最后把结束位置的数和基准数交换观察完成后的数列,可以看到以基准数4为分界线,左边的数全都比4小,右边的数全都比4大。接下来分别对左边的2 3 1和右边的7 6 5重复上面的排序步骤。
2 3 1以2为基准数 -> 2 1 3 -> 1 2 37 6 5以7为基准数 -> 5 6 7我们例子中的数字较少,如果数列足够长,对第一次排序后得到的子数列排序,将再得到两个子数列,然后再一分为二、二分为四。。。直到以基准数拆分后两边都只剩下一个数字。首先来看递归形式的实现代码public class QuickSort { public void sort(int left, int right, int... numbers) { if (left >= right) { return; } int temp = numbers[left]; int t = 0; int i = left; int j = right; while (i != j) { // 先从右往左找 while (numbers[j] >= temp && i < j) j--; // 再从左往右找 while (numbers[i] <= temp && i < j) i++; // 交换两个数在数组中的位置 if (i < j) { t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } } // 将基准数归位 numbers[left] = numbers[i]; numbers[i] = temp; sort(left, i - 1, numbers); sort(i + 1, right, numbers); }}
测试代码
public static void main(String[] args) { int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 }; new QuickSort().sort(0, numbers.length - 1, numbers); System.out.print("after: "); for (int i = 0; i < numbers.length; i++) { System.out.print(numbers[i] + " "); } System.out.println(); }
输出
after: 1 2 3 4 5 6 7
另一种实现方式是使用栈代替递归
public void sortWithoutRecursion(int left, int right, int... numbers) { LinkedListstack = new LinkedList<>(); int index; stack.push(left); stack.push(right); while (!stack.isEmpty()) { right = stack.pop(); left = stack.pop(); index = partition(left, right, numbers); if (left < index - 1) { stack.push(left); stack.push(index - 1); } if (right > index + 1) { stack.push(index + 1); stack.push(right); } } } public int partition(int left, int right, int... numbers) { int temp = numbers[left]; while (left < right) { while (numbers[right] >= temp && left < right) right--; numbers[left] = numbers[right]; while (numbers[left] <= temp && left < right) left++; numbers[right] = numbers[left]; } numbers[left] = temp; return left; }
---------------------
原文:https://blog.csdn.net/autfish/article/details/52368963