题解 | #排序#

import java.util.*;
public class Solution{
    public int[] MySort(int[] arr) {
        qsort(arr,0,arr.length-1);
        return arr;
    }
    
    public void qsort(int []a,int l,int r){
        String step = (l+1) + " " + (r+1);
        int flag = a[l];
        int left = l;
        int right = r;
        int temp =0;
        for(int i = l;i<r+1;i++){
            if (a[i]<flag){//小于移到左边。如果相等，a[i]不动，会被替换
                temp = a[left];
                a[left]=a[i];
                a[i]=temp;
                left++;
                i--;//替换后a坐标不变，将替换后的a[i]值再次比较。for循环退出后，i最终可能小于r+1，但left和right一定相等。
            }else if(a[i]>flag){//大于移到右边
                temp = a[right];
                a[right] =a[i];
                a[i]=temp;
                right--;
                i--;
            }
            if(right==left){
                a[left]=flag;
                break;
            }
        }
        if(left>l){
            qsort(a,l,left-1);
        }
        if(right<r){
            qsort(a,right+1,r);
        }
    }
}