LC101の4. 排序

title: LC101の4. 排序
urlname: yz566z
date: ‘2021-06-08 14:46:14’
tags: [排序]
categories: [算法刷题]

教程

https://zhuanlan.zhihu.com/p/52884590

算法解释

快速排序

思路

找一个基准数，将比它小的丢到左边，比它大的丢到右边
递归地对左右区间做同样操作

图解

代码

void quick_sort(vector<int> &nums, int l, int r) {
    if(l + 1 >= r){
        return;
    }
    int first = l, last = r - 1, key = nums[first];
    while(first < last){
        while(first < last && nums[last] >= key){
            last--;
        }
        nums[first] = nums[last];
        while(first < last && nums[first] <= key){
            first++;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    quick_sort(nums,l,first);
    quick_sort(nums,first + 1,r);
}

归并排序

思路

分成两半，排序，合并
每一半再分成两半，排序，合并
直到分成一个元素，不用排序，直接合并
ps：思想简单，代码简单。合并时需要开辟额外空间，时间复杂度 O(nlogn)

图解

代码

void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp) {
    if (l + 1 >= r) {
        return;
    }
    // divide
    int m = l + (r - l) / 2;
    merge_sort(nums, l, m, temp);
    merge_sort(nums, m, r, temp);
    // conquer
    int p = l, q = m, i = l;
    while (p < m || q < r) {
        if (q >= r || (p < m && nums[p] <= nums[q])) {
            temp[i++] = nums[p++];
        } else {
            temp[i++] = nums[q++];
        }
    }
    for (i = l; i < r; ++i) {
        nums[i] = temp[i];
    }
}

插入排序

思路

每一次将一个待排序地数插入到已排好的数列中，从后往前比较

图解

代码

void insertion_sort(vector<int> &nums, int n){
    for(int i = 0; i < n; i++){
        for(int j = i; j > 0 && nums[j] < nums[j - 1]; j--){
            swap(nums[j], nums[j - 1]);
        }
    }
}

冒泡排序

void bubble_sort(vector<int> &nums, int n){
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - 1 - i; j++){
            if(nums[j] > nums[j + 1]){
                swap(nums[j], nums[j + 1]);
            }
        }
    }
}

选择排序

每次找到最小（大）的放到开头

void selection_sort(vector<int> &nums, int n){
    int mid;
    for(int i = 0; i < n - 1; i++){
        mid = i;
        for(int j = i + 1; j < n; j++){
            if(nums[j] < nums[mid]){
                mid = j;
            }
        }
        swap(nums[mid], nums[i]);
    }
}

测试代码

int main(){
    vector<int> nums = {1,3,5,7,2,6,4,8,9,2,8,7,6,0,3,5,9,4,1,0};
    vector<int> temp(nums.size());
//    quick_sort(nums, 0, nums.size());
//    merge_sort(nums,0,nums.size(),temp);
//    insertion_sort(nums,nums.size());
//    bubble_sort(nums,nums.size());
    selection_sort(nums,nums.size());
    for(int i = 0; i < nums.size(); i++){
        cout<<nums[i]<<' ';
    }
    return 0;
}

快速选择

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int l = 0, r = nums.size() - 1, target = nums.size() - k;
        while(l < r){
            int mid = quickSort(nums, l, r);
            if(mid == target){
                return nums[mid];
            }
            else if(mid < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return nums[l];
    }
    int quickSort(vector<int> &nums, int l, int r){
       int i = l + 1, j = r;
       while(true){
           while(i < r && nums[i] <= nums[l]){
               i++;
           }
           while(l < j && nums[j] >= nums[l]){
               j--;
           }
           if(i >= j)break;
           swap(nums[i], nums[j]);
       }
       swap(nums[l], nums[j]);
       // 比j大的在右，比j小的在左
       return j;
    }
};

桶排序

347. 前 K 个高频元素

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int max_count = 0;
        unordered_map<int, int> counts;
        //统计每个数字出现次数
        for(int i = 0; i < nums.size(); i++){
            max_count = max(max_count, ++counts[nums[i]]);
        }
        //将counts存入buckets（1-3，2-2，3-1）
        vector<vector<int>> buckets(max_count + 1);
        for(const auto & p : counts){
            // cout<<p.second<<' '<<p.first<<endl;
            buckets[p.second].push_back(p.first);
        }
        vector<int> ans;
        int now = max_count, num = 0;
        //将前k个存入ans
        while(now){
            if(num == k)break;
            for(const int & bucket : buckets[now]){
                ans.push_back(bucket);
                num++;
            }
            now--;
        }
        return ans;
    }
};

练习

451. 根据字符出现频率排序

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> num;
        int max_count = 0;
        for(int i = 0; i < s.size(); i++){
            max_count = max(max_count,++num[s[i]]);
        }
        unordered_map<int, string> temp;
        for(const auto & p : num){
            // cout<<p.second<<' '<<p.first<<endl;
            temp[p.second] += p.first;
        }
        string ans = "";
        for(int i = max_count; i > 0; i--){
            if(temp[i] != ""){
                //a,c
                for(int j = 0; j < temp[i].size(); j++){
                    for(int k = 0; k < i; k++){
                        ans += temp[i][j];
                    }
                }
            }
        }
        return ans;
    }
};

75. 颜色分类

class Solution {
public:
    void sortColors(vector<int>& nums) {
        // sort(nums.begin(),nums.end());
        int p = 0, q = nums.size() - 1;
        for (int i = 0; i <= q; ++i) {
            if (nums[i] == 0) {
                nums[i] = nums[p];
                nums[p] = 0;
                ++p;
            }
            if (nums[i] == 2) {
                nums[i] = nums[q];
                nums[q] = 2;
                --q;
                if (nums[i] != 1) {
                    --i;
                }
            }
        }
    }
};