题解 | #排序#

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){
        int mid = a[l];
        int left = l;
        int right = r;
        int temp =0;
        int i=0;
        while(left<right){
             //右边找到比a[l]小的第一个数;和a[l]相等的数不移动，比mid大的数不断后移
             //先right--能确保left和right相等时a[left]<=a[mid],上一轮已经比较替换
            while(a[right]>=mid&&left<right){
                right--;
            }
            //左边找到比a[l]大的第一个数;和a[l]相等的数不移动，比mid小的数不断前移
            while(a[left]<=mid&&left<right){
                left++;
            }
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
               
        }
        //最左边的数a[l]和a[left]替换，一次递归只确定一个数a[l]的位置
        temp = a[left];
        a[left] = a[l];
        a[l] = temp;

        if(left>l){
            qsort(a,l,left-1);
        }
        if(right<r){
            qsort(a,right+1,r);
        }
    }
    //这种方法，当数组中有好多重复值时，会造成mid过多重复移动，超时
    public void qsort2(int []a,int l,int r){
        int mid = a[l];
        int left = l;
        int right = r;
        int temp =0;
        int i=0;
        while(left<right){
            //左边找到比flag大的第一个数;将和mid相等的数不断往中间和后面移动，比mid小的数不断前移
            while(a[left]<mid&&left<right){
                left++;
            }
            //右边找到比flag小的第一个数;将和mid相等的数不断往中间和前面移动，比mid大的数不断后移
            while(a[right]>mid&&left<right){
                right--;
            }
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            //确保和mid相等的数至少一个移到中间
            if (a[left] == mid && a[right] == mid) {
                left++;
            } else if (a[left] != mid && a[right] == mid) {
                left++;
            } else if (a[left] == mid && a[right] != mid) {
                right --;
            } else if (a[left] != mid && a[right] != mid) {
                left++;
                right --;
            }        
        }
       
        if(left>l){
            qsort(a,l,left-1);
        }
        if(right<r){
            qsort(a,right+1,r);
        }
    }

// void Quick_Sort(int [] arr, int begin, int end){
//     if(begin > end)
//         return;
//     int tmp = arr[begin];
//     int i = begin;
//     int j = end;
//     while(i != j){
//         while(arr[j] >= tmp && j > i)//相等的不移动
//             j--;
//         while(arr[i] <= tmp && j > i)
//             i++;
//         if(j > i){//相等的数没比较
//             int t = arr[i];
//             arr[i] = arr[j];
//             arr[j] = t;
//         }
//     }
//     arr[begin] = arr[i];
//     arr[i] = tmp;
//     Quick_Sort(arr, begin, i-1);
//     Quick_Sort(arr, i+1, end);
// }
}