QuickSort

Java

public classQuickSort {
	public int[] quickSort(int[] array) {
		if (array == null || array.length <= 1) {
			return array;
		}
		//overloading here
		quickSort(array, 0, array.length - 1);
		return array;
	}

	private void quickSort(int[] array, int left, int right) {
		//recursion base case
		if (left >= right) {
			return;
		}
		//find pivot position and do partition
		int pivotIndex = findPosAndPartition(array, left, right);
		quickSort(array, left, pivotIndex - 1);
		quickSort(array, pivotIndex + 1, right);
	}
	
	private int findPosAndPartition(int[] array, int left, int right) {
		//random.nextInt(k) → [0, k) / random()[0, 1) → [0, 4)
		Random rn = new Random();
		int pivot = left + rn.nextInt(right - left + 1); //better
		int pivotValue = array[pivot];
		swap(array, pivot, right); //把pivot放在最后
	
		int leftI = left;
		int rightI = right - 1; //array[right] is now the pivot
		
		while (left <= right) {
			if (array[leftI] < pivotValue) {
				leftI++;
			} else if (array[rightI] >= pivotValue) {
				rightI--;
			} else {
				swap(array, leftI++, rightI--);
			}
		}
		//因为之前将pivot放在了right的位置，这后要换回来，放到它应该放的位置
		swap(array, leftI, right); //对调的是值，而不是index
		return leftI;
		}
}


Time Complexity : O(nlogn) → 最坏的情况下是 n^2
Space Complexity : O(1) → 原地交换