题解 | #排序(快排）#

思路：快排。

复杂度：平均时间复杂度O(nlog n),最坏时间复杂度O(n^2),空间复杂度O(n)

代码（JAVA实现）

public class Solution {
	public int[] MySort (int[] arr) {
        if(arr==null||arr.length<2) return arr;
        else quickSort(arr,0,arr.length-1);
        return arr;
    }
	int partition(int[] arr ,int low,int high) {
		int pivot=arr[low];//将第一个数作为枢轴元素
		while(low<high) {
			while(low<high&&arr[high]>=pivot) high--;//从右往左找到比枢轴小的元素
			arr[low]=arr[high];//移到前面
			while(low<high&&arr[low]<=pivot) low++;//从左往右找到比枢轴大的元素
			arr[high]=arr[low];//移到后面
		}
		arr[low]=pivot;//将枢轴放到最终位置
		return low;//返回最终枢轴所在位置
	}
	void quickSort(int[] arr,int low, int high) {
		if(low<high) {
			int pos=partition(arr,low,high);
			quickSort(arr,low,pos-1);//递归对左半区间的数排序
			quickSort(arr,pos+1,high);//递归对右半区间的数排序
		}
	}
}