思路：

指定一个数字，将数组比他小的放到左边，比他大的放到右边，实现归位

然后再指定一个数字递归，一直遍历完数组

最好的情况每次指定的都是中间位置的数字，划分完后两边长度相等，2T(n/2) + O(n)，复杂度O(nlog(n))

可以证明，平均情况下的时间复杂度也是O(nlog(n))

最坏的情况，每次指定的都是最小的数字，n的复杂度归位，一共n次，T(n-1) + O(n)，复杂度O(n^2)

方式一、对撞型指针+指定头元素

class Solution {public int[] sortArray(int[] nums) {trace(nums,0,nums.length - 1);return nums;}public void trace(int[] nums,int start,int end) {if(start>=end){return;}int p = nums[start];int l = start;int r = end;while(l<r){while(nums[r]>=p&&l<r){r--;}nums[l] = nums[r];while(nums[l]<=p&&l<r){l++;}nums[r] = nums[l];}nums[l] = p;trace(nums,l + 1,end);trace(nums,start,l-1);}}

方式二、对撞型指针+指定中间

这里要注意的细节很多，判断条件的时候nums[l]>p不能等于，不然左指针会跑到右边去同理右边

同时l<=r,不能是小于

class Solution {public int[] sortArray(int[] nums) {trace(nums,0,nums.length - 1);return nums;}public void trace(int[] nums,int start,int end) {if(start>=end){return;}int p = nums[(start+end)/2];int l = start;int r = end;while(l<=r){while(nums[r]>p&&l<=r){r--;}while(nums[l]<p&&l<=r){l++;}if(l<=r){swap(nums,l,r);l++;r--;}}trace(nums,start,r);trace(nums,l,end);}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

方式三、快慢指针+指定尾元素

lass Solution {public int[] sortArray(int[] nums) {partition(nums, 0, nums.length - 1);return nums;}public void partition(int[] nums, int l, int r) {if(l<r){int pivot = nums[r];int i = l - 1;//快慢指针找到目标位置for (int j = l; j <= r - 1; ++j) {if (nums[j] <= pivot) {i = i + 1;swap(nums, i, j);}}//放置目标元素swap(nums, i + 1, r);int p = i+1;//递归partition(nums,l,p-1);partition(nums,p+1,r);}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}