快排 & 堆排序

排序

排序一直是很基础的一个问题。

复习快排 &堆排序。

LeetCode215 找第k大的元素

快排

注意事项：

1、排序的时候，是先右边标兵while，再左边标兵while。这是因为我们一般选择左一作为基准数据，右边标兵先遇到不符合右边标准的停住，显然这个数是符合左边标准的（左指针在指），因此可以和左一互换，是合理的。

2、中间有个ll>rr的break。也可以判断，当＜的时候再交换。

快排的边界很烦。

class Solution {
public:
    int quicksort(int lb,int rb,vector<int>& nums, int k){
        // if(lb)
        int ll=lb;
        int rr=rb;
        if(lb>rb || lb<0 || rb>nums.size()-1)
            return -1;
        while(ll<rr){
            while(nums[rr]<=nums[lb]&&ll<rr)
                rr-=1;
            while(nums[ll]>=nums[lb]&&ll<rr)
                ll+=1;
            if(ll>rr)
                break;
            swap(nums[ll],nums[rr]);

        }
        swap(nums[lb],nums[ll]);
        // cout<<nums[0]<<nums[1]<<nums[2]<<nums[3]<<nums[4]<<nums[5]<<endl;
        if(ll==k-1)
            return nums[ll];
        int x = quicksort(lb,ll-1,nums,k);
        int y =quicksort(ll+1,rb,nums,k);
        if(x!=-1)
            return x;
        if(y!=-1)
            return y;
        
        return -1;
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quicksort(0,nums.size()-1,nums,k);
    }
};

用函数

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

堆排序

1、建堆。

使用自上而下调整，建堆方法是，从有子节点的节点开始，倒序，自上向下调整。

2、删除节点，得到第k个。

也是自上而下调整。

3、细节。

先左右比，得到需要换的节点，然后再和父节点换。

注意 从0开始排，两个子节点就是2i+1和2i+2

class Solution {
public:
    void downjust(vector<int>& nums,int i){
        int len=nums.size();
        while(i<len){
            int l=i*2+1;
            int r=i*2+2;
            int index = i;
            if(r<len&&nums[l]<nums[r]&&nums[i]<nums[r]){//选最大的交换
                    index=r;
            }else if(l<len&&nums[i]<nums[l]){
                    index=l;
            }
            if(index==i)
                return;
            else
                swap(nums[i],nums[index]);
            i=index;
            
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        // sort(nums.begin(),nums.end());
        //建堆。。第k大的是删到第k个？
        for(int i=nums.size()/2;i>=0;i--){//nums.size()-1or nums.size()
            downjust(nums,i);
        }
        //删到第k个
        for(int i=0;i<k-1;i++){

            nums[0]=nums[nums.size()-1];
            nums.pop_back();//每次删除一个
            downjust(nums,0);
            
        }
        
        return nums[0];
    }
};

官方解答，注意不同的地方

官方解答，无需删除最后一个元素，而是交换，然后利用heapsize减少专注前heapsize个元素。

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);//使用了递归
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);//使用交换的方法，不是直接覆盖
            --heapSize;//heapsize每次都减少，专注前heapsize个数
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(n log n)，建堆的时间代价是 O(n)，删除的总代价是 O(klogn)，因为 k < n，故渐进时间复杂为 O(n + klog n) = O(n log n)。
空间复杂度：O(logn)，即递归使用栈空间的空间代价。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。