public int[] quickSort(int[] nums){ if(nums == null || nums.length == 0){ return nums; } System.out.print("Original nums[] is: "); printIntArray(nums); quickSortHelper(0, nums.length - 1, nums); return nums; } public void quickSortHelper(int left, int right, int[] nums){ if(left >= right){ return; } //为什么这里要把left，right重新赋值给l,r？ //是因为l,r需要在while过程中变动去交换值，而left，right是为了递归，直到进入下一个递归前，需要需要保持不变 int l = left; int r = right; int temp; //l<r的条件控制，放在子while中去控制。这里只控制l != r，因为当l == r时，会跳出循环，触发benchmark与nums[l]/nums[r]交换 while(l != r){ //加入l < r，防止移动过程中出现l >= r, nums[left]作为benchmark while(nums[r] >= nums[left] && l < r){ r--; } //加入l < r，防止移动过程中出现l >= r, nums[left]作为benchmark while(nums[l] <= nums[left] && l < r){ l++; } //这时候，不一定l==r了， 也有可能是各自找到符合条件的，但还没有最终汇合 if(l < r){ temp = nums[r]; nums[r] = nums[l]; nums[l] = temp; System.out.print("Swap nums[l] and nums[r]: "); printIntArray(nums); } } //当l,r汇合后，触发benchmark与nums[l]/nums[r]交换 temp = nums[left]; nums[left] = nums[l]; nums[l] = temp; if(left < right){ System.out.print("After finish one process: "); printIntArray(nums); } //递归 quickSortHelper(left, l - 1, nums); quickSortHelper(l + 1, right, nums); } public void printIntArray(int[] nums){ for(int num : nums){ System.out.print(num + " "); } System.out.print("\n"); } public static void main(String[] args){ Solution solution = new Solution(); int[] ints = new int[]{6,1,2,7,9,3,4,5,10,8}; solution.quickSort(ints); }
运行结果：
Original nums[] is: 6 1 2 7 9 3 4 5 10 8 Swap nums[l] and nums[r]: 6 1 2 5 9 3 4 7 10 8 Swap nums[l] and nums[r]: 6 1 2 5 4 3 9 7 10 8 After finish one process: 3 1 2 5 4 6 9 7 10 8 After finish one process: 2 1 3 5 4 6 9 7 10 8 After finish one process: 1 2 3 5 4 6 9 7 10 8 After finish one process: 1 2 3 4 5 6 9 7 10 8 Swap nums[l] and nums[r]: 1 2 3 4 5 6 9 7 8 10 After finish one process: 1 2 3 4 5 6 8 7 9 10 After finish one process: 1 2 3 4 5 6 7 8 9 10
方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。
ref:https://blog.csdn.net/csdnqixiaoxin/article/details/89429528
下例中，i对应着l, j对应着r。
temp = a[left]; //temp中存的就是基准数 i = left; j = right; while(i != j) { //顺序很重要，要先从右边开始找 while(a[j] >= temp && i < j) j--; while(a[i] <= temp && i < j)//再找右边的 i++; if(i < j)//交换两个数在数组中的位置 { t = a[i]; a[i] = a[j]; a[j] = t; } } //最终将基准数归位 a[left] = a[i]; a[i] = temp;
可以看到，一次遍历的终止条件是哨兵i和哨兵j相遇了，这个时候将基准数与i,j位置的元素进行交换。而哨兵i和哨兵j相遇会在以下两种情况下发生：
哨兵j向左扫描的过程中，主动和哨兵i相遇，即第5行那个while循环第二个条件不满足。
哨兵i向右扫描的过程中，主动和哨兵j相遇，即第7行那个while循环第二个条件不满足。
下面我们看一下在两种情况下，相遇时元素的大小：
在第一种情况下，相遇时候的元素一定小于等于基准数。因为哨兵i还没动，所以我们只要考察哨兵i所在位置的大小。而哨兵i所在位置一定是小于等于基准数的，因为一开始，哨兵i就是基准数，而在后续交换的过程中，会将哨兵j找到的小于基准数的元素换到了哨兵i的位置。因此，这时候，我们将基准数与相遇位置的元素进行交换，得到的序列一定满足基准数左边元素都小于等于基准数，右边元素都大于等于基准数。
在第二种情况下，相遇时候的元素一定小于基准数。这种情况下，哨兵j已经找到了比基准数小的元素，哨兵i右移的过程中与其相遇。因此，这时候，我们将基准数与相遇位置的元素进行交换，得到的序列也一定满足基准数左边元素都小于等于基准数，右边元素都大于等于基准数。
可以看到，让哨兵j先走是正确的。那么，如果让哨兵i先走会发生什么？
假设让哨兵i先走，则代码改成这样：
while(i != j) { while(a[i] <= temp && i < j) i++; while(a[j] >= temp && i < j) j--; if(i < j)//交换两个数在数组中的位置 { t = a[i]; a[i] = a[j]; a[j] = t; } }
哨兵i和哨兵j相遇也会在两种情况下发生：
哨兵i向右扫描的过程中，主动和哨兵j相遇，即第2行那个while循环第二个条件不满足。
哨兵j向左扫描的过程中，主动和哨兵i相遇，即第4行那个while循环第二个条件不满足。
再看一下在两种情况下，相遇时元素的大小：
在第一种情况下，哨兵j还没动，但哨兵j所在位置要么不确定大小（一开始的时候），要么比基准数大（上次交换之后）。所以这时候不能将基准数与相遇位置的元素进行交换。
在第二种情况下，哨兵i已经找到比基准数大的数，哨兵j在左移的过程中与其相遇。这时候也不能将基准数与相遇位置的元素进行交换。
所以，让哨兵i先走的话逻辑就不对了。当然，在这种情况下，也可以添加额外的处理逻辑，比如让相遇位置前一个元素与基准数进行交换、比较相遇位置与基准数的大小。但何必使代码复杂化呢？
同理，如果我们选最右边的元素作为基准数，就应该让哨兵i先走了。
原文：https://www.cnblogs.com/frankcui/p/11538170.html