朝花夕拾

void solution(int[] arr, int lo, int hi){
	// 递归退出条件
    if(lo >= hi) {
    	return;
    }
    
    // 分区 核心部分
    int pos = partition(arr, lo, hi);
    
    // 递归排序子数组
    solution(arr, lo, pos - 1);
    solution(arr, pos + 1, hi);
}

void patition(int[] arr, int lo, int hi) {

    // 定义扫描指针
    int l = lo;
    int r = hi + 1;
    
	// 确定基准位元素
    int seed = arr[lo];
    
    // 开始扫描
    while(true) {
    	
        // 从左向右
        while(arr[++l] <= seed) {
        	// 达到最大搜索区间，退出
            if(l == hi) {
            	break;
            }
        }
        
        // 从右向左
        while(arr[--r] >= seed) {
        	// 达到最小搜索区间，退出
            if(r == lo) {
            	break;
            }
        }
        
        // 找到了基准位置r，退出循环
        if(r <= l) {
            break;
        }
        
        // 尚未找到基准位置，需要后续继续扫描，当前左右指针位置数据进行交换
        switch(arr, r, l);
    }
    
    // 将基准位元素放置到争取的位置
    switch(arr, lo, r);
    
    // 返回基准位
    return r;
}

### 遍历左指针可能情况
case l == lo
	//这种情况不可能出现，因为左指针的起始扫描位置就是lo+1
case lo < l < hi
	//左指针在中间位置 此时一定满足 a[r]>base && a[i{i < r}] <= base
    case l > r
    	// 这时，说明数字排序比较乱，a[l]<base && a[i{i>l}] >= base
        // 在r和l之间存在倒序的情况
        // 这时直接对r,l两个元素进行交换
    case l < r
    	// 这里出现了一个临界点j，临界点左边的元素都小于base 右边的元素都大于base
        // 那么，这时只需要把临界点前面的元素与base交换即可。
    case l == r
    	// 由上面公式可知，达到临界点j时，l还会再扫描一次，变更j+1
        // r也会扫描一次，变成j-1 所以r和j不会在临界点相遇
case l==hi
	case r == hi
    // 当数组中原有元素都比基准位小时，左指针会达到最大搜索区间，同时，右指针也会停在最大搜索区间
    case r < hi
    // 右上可知，这种情况不存在