排序算法

排序算法

215 数组中的第K个最大元素

方法一：快速排序

//快速排序
//左闭右开
void quick_sort(vector<int>& nums, int l, int r) {
    //如果数组大小为1，则无需排序
    if (l + 1 >= r) {
        return;
    }
    //因为传入的是nums.size()所以要减1
    int first = l, last = r - 1, key = nums[first];
    //确定中心点位置为first
    while (first < last) {
        while (first < last && nums[last] >= key) {
            --last;
        }
        //从后往前，找到比key值小的数，搬到first的位置
        nums[first] = nums[last];
        while (first < last && nums[first] <= key) {
            ++first;
        }
        //从前往后，找到比key值大的数，搬到刚才空出来的last的位置
        nums[last] = nums[first];
    }
    //把key值赋给first位，此时的first=last
    nums[first] = key;
    //对低子表递归排序
    quick_sort(nums, l, first);
    //对高子表递归排序
    quick_sort(nums, first + 1, r);
}

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

方法二：sort排序

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

方法三：优先队列，小顶堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> res;
        for (auto& a : nums) {
            res.push(a);
            if (res.size() > k)
                res.pop();
        }
        return res.top();
    }
};

347 前K个高频元素

方法一：桶排序

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counts;
        int max_count = 0;
        //查找最大频次
        //根据每个数的频次放入unordered_map容器 1:4, 2:2, 3:1, 4:1
        for (const int& num : nums) {
            max_count = max(max_count, ++counts[num]);
        }
        //按照频次建立4个新桶，1:[3,4], 2:[2], 3:[1], 4:[1]
        vector<vector<int>> buckets(max_count + 1);
        for (const auto& p : counts) {
            buckets[p.second].push_back(p.first);
        }
        //从后往前遍历，直到找到k个频次最高的桶
        vector<int> ans;
        for (int i = max_count; i >= 0 && ans.size() < k; --i) {
            for (const int& num : buckets[i]) {
                ans.push_back(num);
                if (ans.size() == k) {
                    break;
                }
            }
        }
        return ans;
    }
};

532 数组中的k-diff数对

方法1：排序+二分查找

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int n=nums.size(),res=0;
        // 对数组进行排序
        sort(nums.begin(),nums.end());
        // 从左到右比遍历，在[i+1，n-1]的范围内二分查找nums[i]+k是否存在即可
        for(int i=0;i<n-1;i++){
            // 重复的不计算
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int target=nums[i]+k;
            int left=i+1,right=n-1;
            int ans=-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(nums[mid]>=target){
                    ans=mid;
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
            // 判断是否找到
            if(ans!=-1 && nums[ans]==target){
                res++;
            }
        }
        return res;
    }
};

912 排序数组

方法1：冒泡排序（超时）

冒泡排序是从左到右依次比较相邻的两个元素，如果前一个元素比较大，就把前一个元素和后一个交换位置，遍历数组之后保证最后一个元素相对于前面的永远是最大的。然后让最后一个保持不变，重新遍历前n-1个元素，保证第n-1个元素在前n-1个元素里面是最大的。依此规律直到第2个元素是前2个元素里面最大的，排序就结束了。

因为这个排序的过程很像冒泡泡，找到最大的元素不停的移动到最后端，所以这个排序算法就叫冒泡排序。

冒泡排序的最大特点就是代码简单，短短的五行代码就能完成整个排序的操作。

时间复杂度比较稳定不管怎样都需要O(n^2)次比较，时间复杂度

空间复杂度是O(1)，所有操作在原来的数组完成就可以了，不需要额外的空间。

算法是稳定的，在冒泡的过程中如果两个元素相等，那么他们的位置是不会交换的。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(nums[j]>nums[j+1]){
                    swap(nums[j], nums[j+1]);
                }
            }
        }
        return nums;
    }
};

插入排序（超时）

选择排序（超时）

快速排序（超时）

因为有很极端的例子，全部相等、或者倒序，让时间复杂度恶化为\(O(n^2)\)

方法2：希尔排序（可过）

class Solution {
public:
    void shell(vector<int>& nums, int gap, int i){
        int inserted=nums[i];
        int j;
        for(j=i-gap;j>=0 && inserted<nums[j];j-=gap){
            nums[j+gap]=nums[j];
        }
        nums[j+gap]=inserted;
    }

    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        for(int gap=len/2;gap>0;gap/=2){
            for(int i=gap;i<len;i++){
                shell(nums, gap, i);
            }
        }
        return nums;
    }
};

方法3：归并排序（可过）

class Solution {
public:
    void sort(vector<int>& nums, vector<int>& numsTemp, int low, int high){
        if(low>=high) return;
        int len =high-low;
        int mid=low+len/2;
        int start1=low, end1=mid, start2=mid+1, end2=high;
        sort(nums, numsTemp, start1, end1);
        sort(nums, numsTemp, start2, end2);
        int index=low;
        while(start1<=end1 && start2<=end2){
            numsTemp[index++]=nums[start1]<nums[start2]?nums[start1++]:nums[start2++];
        }

        while(start1<=end1){
            numsTemp[index++]=nums[start1++];
        }
        while(start2<=end2){
            numsTemp[index++]=nums[start2++];
        }

        for(index=low;index<=high;++index){
            nums[index]=numsTemp[index];
        }
    }


    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        vector<int> numsTemp(len, 0);
        sort(nums, numsTemp, 0, nums.size()-1);
        return nums;
    }
};

方法4：堆排序（可过）

class Solution {
public:
    void heapify(vector<int>& nums, int n, int i){
        int l=i*2+1;
        int r=i*2+2;
        int max=i;
        if(l<n && nums[l]>nums[max]) max=l;
        if(r<n && nums[r]>nums[max]) max=r;
        if(max!=i){
            swap(nums[max], nums[i]);
            heapify(nums, n, max);
        }
    }

    void heapify_build(vector<int>& nums, int n){
        int parent=(n-2)/2;
        for(int i=parent;i>=0;i--){
            heapify(nums, n, i);
        }
    }


    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        heapify_build(nums, n);
        for(int i=0;i<n;i++){
            swap(nums.front(), nums[n-i-1]);
            heapify(nums, n-i-1, 0);
        }
        return nums;
    }
};

方法4：堆排序（就记这个）

class Solution {
public:
    /* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
    void shiftDown(vector<int>& nums, int n, int i){
        while(true){
            int l=2*i+1;
            int r=2*i+2;
            int ma=i;
            if(l<n && nums[l]>nums[ma]){
                ma=l;
            }
            if(r<n && nums[r]>nums[ma]){
                ma=r;
            }
            if(ma==i){
                break;
            }
            swap(nums[ma], nums[i]);
            i=ma;
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        for(int i=(n-2)/2;i>=0;i--){
            shiftDown(nums, n, i);
        }

        for(int i=nums.size()-1;i>0;i--){
            swap(nums[0], nums[i]);
            shiftDown(nums, i, 0);
        }
        return nums;
    }
};