快速排序：

• 分：找到分成兩部分進行排序的pos（使用partition）
• 治：分別對這兩部分進行快速排序

重點：partition
找到pivot（兩個方法：1. 取第一個值；2. 取隨機值），并放在區間的最右邊
設定pointer作為最終要返回的pos，實際代表的是pivot的位置，其左邊元素均小于pivot，右邊元素均大于pivot
于是對區間內元素進行遍歷，如果小于pivot，將其放在pointer的位置，并將pointer+1
遍歷結束后，將pivot放到pointer它應該在的位置
返回pointer（即pos）

class Solution {public int[] sortArray(int[] nums) {// 快速排序quickSort(nums, 0, nums.length - 1);return nums;}// 快速排序public void quickSort(int[] nums, int low, int high) {// while (low < high) {if (low < high) {int pos = partition(nums, low, high);quickSort(nums, low, pos - 1);quickSort(nums, pos + 1, high);}}public int partition(int[] nums, int l, int r) {int pivotIndex = l + new Random().nextInt(r - l + 1);swap(nums, pivotIndex, r);int pivot = nums[r];int pointer = l;for (int i = l; i < r; ++i) {// if (nums[i] < nums[pointer]) {if (nums[i] < pivot) {swap(nums, i, pointer);pointer++;}}swap(nums, pointer, r);return pointer;}public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}