排序经典题

快速排序

public void quickSort(int nums[],int start,int end){
    ....
    partition(..);//可以不封装
    ....
    quickSort(..);
    qucikSort(..);
}

• 一次划分过程是和sentinel的值比较
• 没有swap, 不止不断交替写值

  快速排序实现一

  快速排序实现二

  快速排序优化-随机化选择哨兵

求第topK大\K小元素 or 求topK大\K小元素子数组

求解top K小元素，和求解top K个小元素（字数组），过程，截止条件是一样的。区别只是return 而已

• 思路一：全体排序，返回前k个
• 二：快速排序，单边划分寻找
  • 两种情况的处理巧妙的是一致的
  • 快排中，当你找到pos=k，那么左边的元素全小于num[k] , 尽管还无序，但满足求topK大\K小元素子数组了，没要求结果子数组有序！
  • 代码上，把 target pos 当作全局的位置加以判断，不需要在递归的过程修改target pos . 因为partition函数返回的一次 pos, 也是全局的Index。 比如剑指P206的做法。
• 三：大根堆

注意：中位数 k = len/2, 实际是滴k+1大的数。可以这么记，topk大还是小，还是中位数，最后转化为目标pos数组的位置来判断。

快速选择代码

public int randomPartition(int[] nums,int start,int end){
           //
        if(start>=end) return start;
        //1.确定sentimal
        //要不要做随机化
        Random random = new Random();
        int exchangePos = start + random.nextInt(end-start+1);
        int sentinel = nums[exchangePos];
        int tem = nums[start];
        nums[start] = nums[exchangePos];
        nums[exchangePos] = tem;
        //2确定扫描界
        int left = start;
        int right = end;
        //3.开始扫描：注意，不断交替，出来时是 left=right
        while(left<right){
            while(nums[right]>=sentinel && left<right) right--;
            nums[left] = nums[right];
            while(nums[left]<= sentinel && left<right) left++;
            nums[right] = nums[left];
        }
        //4.不要忘记放置哨兵
        nums[left] = sentinel;
        //5.最后返回position
        return left;
    }

参考代码：

• 超出数组一半的数，转寻找中位数，随机化快速选择 (但此题有更好的解法，虽然时间复杂度一样) ```java public int majorityElement(int[] nums) {

    //解法一 用基于快排的随机快速选择，选择中位数
    int k = nums.length/2;
    return quickSelectKpos(nums,0,nums.length-1,k);

}
public int quickSelectKpos(int[]nums,int start,int end,int k){
    int partiPos = randomPartition(nums,start,end);
    if(partiPos == k) return nums[k];
    else if(partiPos <k ){
        return quickSelectKpos(nums,partiPos+1,end,k);
    }else return quickSelectKpos(nums,start,partiPos-1,k);
}
public int randomPartition(int[] nums,int start,int end){
    if(start>=end) return start;
    Random random = new Random();
    int exchangePos = start + random.nextInt(end-start+1);
    int sentinel = nums[exchangePos];
    int tem = nums[start];
    nums[start] = nums[exchangePos];
    nums[exchangePos] = tem;
    int left = start;
    int right = end;
    while(left<right){
        while(nums[right]>=sentinel && left<right) right--;
        nums[left] = nums[right];
        while(nums[left]<= sentinel && left<right) left++;
        nums[right] = nums[left];
    }
    //最后这里忘记放置哨兵了
    nums[left] = sentinel;
    return left;
}

```