前置题目：可先学习相对更简单的快速选择算法，重点掌握划分（partition）的原理，题目见hot100 215.数组中的第K个最大元素。
思路：手写快排。
1.快速排序的核心思想：
（1）定义一个递归函数sort(left,right)，表示把子数组[left,right]升序排列。
（2）划分子数组[left,right]，划分方法同hot100 215.数组中的第K个最大元素。设划分后，基准元素pivot的下标为i。
（a）在pivot左侧的元素，继续递归排序，即递归调用sort(left,i - 1)。
（b）在pivot右侧的元素，继续递归排序，即递归调用sort(i + 1,right)。
（3）递归边界：如果left >= right，说明子数组为空或者只剩一个元素，此时无需排序，直接返回。
（4）递归入口：sort(0,n - 1)。
2.优化：如果子数组已是升序数组，直接返回。
3.疑问：
（1）如果不随机选择基准元素pivot，会发生什么？
答：
如果子数组是降序的，且我们每次都选子数组的第一个（或者最后一个）元素作为pivot，那么按照算法，j不变或者移动到最左边，划分是最不均匀的，算法会退化至O(n^2)。随机选择pivot的目的是能使划分在期望意义上是均匀的（j移动到子数组的中间），保证算法的期望时间复杂度为O(nlogn)。
（2）代码中的nums[i] < pivot和nums[i] > pivot，能否改成nums[i] <= pivot和nums[i] >= pivot？
答：
这个做法会在子数组所有元素相同时，划分后的j是子数组的最后一个元素的下标，是最不均匀的划分，算法也会退化至O(n^2)。
（3）代码中的i <= j能否改成i < j？
答：
这样的话会算错。来看一个例子nums = [2,1,3]，pivot = 2。
（a）左指针i = 1移动到i = 2，右指针j = 2因为不满足i < j的条件，无法移动。此时我们交换2和nums[j] = 3，得到[3,1,2]，返回j = 2。然而j = 2的左侧有大于pivot = 2的元素，划分失败。
（b）如果写成i <= j，那么最终i = 2,j = 1。此时我们交换2和nums[j] = 1，得到[1,2,3]，返回j = 1。这样的划分就是正确的。
4.复杂度分析：
（1）期望时间复杂度：O(nlogn)，其中n是nums的长度。在平均情况下，可以视作均匀划分（partition）。递归深度为O(logn)，每一层都会涉及O(n)个元素的比较和交换，所以时间复杂度等于一个高为O(logn)，底边长为O(n)的矩形的面积，即O(nlogn)。
（2）期望空间复杂度：O(logn)。递归需要期望O(logn)的栈开销。
5.总结：
附代码：
class Solution { private static final Random rand = new Random(); public int[] sortArray(int[] nums) { quickSort(nums,0,nums.length - 1); return nums; } // 快速排序子数组[left,right] private void quickSort(int[] nums,int left,int right){ // 优化：如果子数组已经升序，直接返回 boolean ordered = true; for(int i = left;i < right;i++){ if(nums[i] > nums[i + 1]){ ordered = false; break; } } if(ordered){ return; } // 接收pivot最终的位置，满足pivot前面的元素都小于pivot，pivot后面的元素都大于pivot int i = partition(nums,left,right); quickSort(nums,left,i - 1); // 排序在 pivot 左侧的元素 quickSort(nums,i + 1,right); // 排序在 pivot 右侧的元素 } // 在子数组[left,right]中随机选择一个基准元素pivot // 根据pivot重新排列子数组[left,right] // 重新排列后，<= pivot的元素都在pivot的左侧，>= pivot的元素都在pivot的右侧 // 返回pivot在重新排列后的nums中的下标 // 特别地，如果子数组的所有元素都等于pivot，我们会返回子数组的中心下标，避免退化 private int partition(int[] nums,int left,int right){ // 1.在子数组[left,right]中随机选择一个基准元素pivot // rand.nextInt(int bound)表示生成一个范围在[0,bound)之间的随机整数 int i = left + rand.nextInt(right - left + 1); int pivot = nums[i]; // 把pivot与子数组第一个元素交换，避免pivot干扰后续划分，从而简化实现逻辑 swap(nums,i,left); // 2. 相向双指针遍历子数组 [left + 1, right] // 循环不变量：在循环过程中，子数组的数据分布始终如下图 // [ pivot | <=pivot | 尚未遍历 | >=pivot ] // ^ ^ ^ ^ // left i j right i = left + 1; int j = right; // 每走一步都会：i++或者j-- // 数组长度有限，因此也不会无限循环下去 while(true){ while(i <= j && nums[i] < pivot){ i++; } // 此时nums[i] >= pivot while(i <= j && nums[j] > pivot){ j--; } // 此时nums[j] <= pivot if(i >= j){ break; } // 维持循环不变量 swap(nums,i,j); i++; j--; } // 循环结束后 // [ pivot | <=pivot | >=pivot ] // ^ ^ ^ ^ // left j i right // 3. 把 pivot 与 nums[j] 交换，完成划分（partition） // 为什么与 j 交换？ // 如果与 i 交换，可能会出现 i = right + 1 的情况，已经下标越界了，无法交换 // 另一个原因是如果 nums[i] > pivot，交换会导致一个大于 pivot 的数出现在子数组最左边，不是有效划分 // 与 j 交换，即使 j = left，交换也不会出错 swap(nums,left,j); // 交换后 // [ <=pivot | pivot | >=pivot ] // ^ // j // 返回 pivot 的下标 return j; } // 交换 nums[i] 与 nums[j]，即索引位置对应的元素值 private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }ACM模式：
import java.util.Random; import java.util.Scanner; class Solution { private static final Random rand = new Random(); public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } // 快速排序子数组[left,right] private void quickSort(int[] nums, int left, int right) { // 优化：如果子数组已经升序，直接返回 boolean ordered = true; for (int i = left; i < right; i++) { if (nums[i] > nums[i + 1]) { ordered = false; break; } } if (ordered) { return; } // 接收pivot最终的位置，满足pivot前面的元素都小于pivot，pivot后面的元素都大于pivot int i = partition(nums, left, right); quickSort(nums, left, i - 1); quickSort(nums, i + 1, right); } // 在子数组[left,right]中随机选择一个基准元素pivot // 根据pivot重新排列子数组[left,right] // 重新排列后，<= pivot的元素都在pivot的左侧，>= pivot的元素都在pivot的右侧 // 返回pivot在重新排列后的nums中的下标 private int partition(int[] nums, int left, int right) { // 1.在子数组[left,right]中随机选择一个基准元素pivot int i = left + rand.nextInt(right - left + 1); int pivot = nums[i]; // 把pivot与子数组第一个元素交换 swap(nums, i, left); // 2. 相向双指针遍历子数组 [left + 1, right] i = left + 1; int j = right; while (true) { while (i <= j && nums[i] < pivot) { i++; } while (i <= j && nums[j] > pivot) { j--; } if (i >= j) { break; } swap(nums, i, j); i++; j--; } // 3. 把 pivot 与 nums[j] 交换，完成划分 swap(nums, left, j); return j; } // 交换 nums[i] 与 nums[j] private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取数组长度 int n = scanner.nextInt(); // 读取数组元素 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } // 排序数组 Solution solution = new Solution(); int[] result = solution.sortArray(nums); // 输出排序后的数组 for (int i = 0; i < result.length; i++) { System.out.print(result[i]); if (i < result.length - 1) { System.out.print(" "); } } scanner.close(); } }
