Sort Integers II

Java

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
		public void sortIntegers2(int[] A) {
			if (A == null) return;
			helper(A, 0, A.length - 1);
		}
		
		private void helper(int[] A, int left, int right) {
			if (left >= right) {
				return;
			}
			
			int pivot = A[left + (int)(Math.random() * (right - left)];    //选 pivot 套路
			int i = left, j = right;
			
			while (i <= j) {
				while (i <= j && A[i] < pivot) {
					i++;
				}
		
				while (i <= j && A[j] > pivot) {
					j--;
				}
			
				if (i <= j) {
					int t = A[i];
					A[i++] = A[j];
					A[j--] = t;
				}
			}
			helper(A, left, j);
			helper(A, i, right);
		}
}



Time Complexity : O(nlogn) → 最坏的情况下是 n^2
Space Complexity : O(logn) 平均情况 - 递归的过程中需要空间消耗
			- O(n) 最坏情况