题解 | #排序#

最想说的是这个快速排序

public class Solution {
 
    public int partition(int[] arr,int low,int high)
    {

        int pivot=arr[high];//枢轴元素
        int pointer=low;
        for(int i=low;i<high;i++)
        {
            if(arr[i]<=pivot)
            {
                int temp=arr[i];
                arr[i]=arr[pointer];
                arr[pointer]=temp;//交换当前元素和当前指针所指的元素
                pointer++;
            }
        }
        //交换枢轴和当前指针指向的位置的值
        arr[high]=arr[pointer];
        arr[pointer]=pivot;
        return pointer;
    }
    public void quicksort(int[] arr,int low,int high)
    {
        if(low<high)
        {
            int pivot=partition(arr,low,high);
            quicksort(arr,low,pivot-1);
            quicksort(arr,pivot+1,high);        
        }
    }
    
    
    public int[] MySort (int[] arr) {
        // write code here
        //1.哈哈排序
//         Arrays.sort(arr);
//         return arr;
        //2.快速排序  1）partition 划分  2）排序
        quicksort(arr,0,arr.length-1);      
        return arr;
     
    }
}

快速排序分为三大块：1.划分（partition）2.quicksort 3. main function

划分是最核心的 每一趟划分，我们把high处的元素值暂存到pivot中，让他站到一边，做一个哨兵。 然后用一个指针pointer从low的地方开始遍历，当当前元素小于哨兵的时候，就把这个元素和pointer所指的元素交换，然后pointer后移 这样的作用是，当遍历到pivot前面一位的时候，pointer所指的地方恰好是pivot应该在的地方，这样最后再交换一下pointer所指值和pivot的值，就得到了一个 一趟排序后的数组 返回pivot的值 这样一趟的时间复杂度是logn

在quicksort函数中，两边不断递归，直到得到有序的数组

总的时间复杂度是nlogn

完美