Java版快速排序[不稳定]

Answer 1

原理：分治+递归

复杂度：O(nlgn) - O(nlgn) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]

栈空间0(lgn) - O(n)

// 固定基准
public void quickSort(int[] a, int low, int high) {
		if (null == a || a.length < 2) {
			return;
		}
		if (low < high) {
			int mid = partition(a, low, high);
			quickSort(a, low, mid-1);
			quickSort(a, mid+1, high);
		}
	}

	private int partition(int[] a, int low, int high) {
		int pivot = a[low];

		while (low < high) {
			// 注意等于，否则死循环
			while (low < high && a[high] >= pivot) {
				high--;
			}
			a[low] = a[high];
			// 注意等于，否则死循环
			while (low < high && a[low] <= pivot) {
				low++;
			}
			a[high] = a[low];
		}
		a[low] = pivot;
		
		return low;
	}