Leetcode 刷题笔记-Leetcode 101 第5章 排序算法

Leetcode 刷题笔记-Leetcode 101 第5章 排序算法

排序算法

排序自然都有C++的STL搞定了，但是在实际中仍然需要这些排序算法，一方面夯实基础，另一方面有一些题目是从这些排序算法中引申出来的，掌握这些排序算法对于做题也会有很大的帮助。

常用排序算法

调用

int main(void){
    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());
    sort(nums.begin(), nums.end());
    quick_sort(nums, 0, nums.size());
    print(nums);
    merge_sort(nums, 0, nums.size(), temp);
    print(nums);
    insertion_sort(nums, nums.size());
    print(nums);
    bubble_sort(nums, nums.size());
    print(nums);
    selection_sort(nums, nums.size());
    print(nums);
    return 0;
}

快速排序

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

错误：while内部的 left < right的条件没有加，导致内部会出问题，而且也是要+1的

归并排序

void merge_sort(vector<int> &nums,int left,int right,vector<int> &temp){
    if(left + 1 >= right){
        return;
    }
    int mid = (right - left) / 2 + left;
    merge_sort(nums,left,mid,temp);
    merge_sort(nums,mid,right,temp);
    int p = left;
    int q = mid;
    int i = left;
    while(p < mid && q < right){
        if(nums[p] <= nums[q]){
            temp[i++] = nums[p++];
        }
        else{
            temp[i++] = nums[q++];
        }
    }
    while(p < mid){
        temp[i++] = nums[p++];
    }
    while(q < right){
        temp[i++] = nums[q++];
    }
    for(int j=left;j<right;++j){
        nums[j] = temp[j];
    }
}

错误：应该是 left + 1 >= right，只剩下一个数字后就应该返回了。

插入排序

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

冒泡排序

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

选择排序

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

快速排序

Leetcode 215

在一个未排序的数组中，找到第 k大的数字

class Solution {
public:
    static void quick_selection(vector<int> &nums,int left,int right,int k){
        int l = left;
        int r = right;
        int k2 = nums[left];
        if(left + 1 > right){
            return;
        }
        while(left+1 < right){
            while(left+1 < right && nums[right-1] < k2){
                --right;
            }
            nums[left] = nums[right-1];
            while(left+1 < right && nums[left] >= k2){
                ++left;
            }
            nums[right-1] = nums[left];
        }
        nums[left] = k2;
        if(k <= left){
            quick_selection(nums,l,left,k);
        }
        else{
            quick_selection(nums,left+1,r,k);
        }
        return;
    }
    int findKthLargest(vector<int>& nums, int k) {
        quick_selection(nums,0,nums.size(),k-1);
        return nums[k-1];
    }
};

分析：与快速排序相同的思路，但是不需要对没有用的一侧进行快速排序，只需要对k在的区间一侧进行快速排序即可。

错误：开始快速排序有问题，然后k的值想不清楚造成错误。

桶排序

Leetcode 347

class Solution {
public:
    static bool cmp(pair<int,int> &a,pair<int,int> &b){
        return a.first > b.first;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> mp1,mp2;
        for(auto i : nums){
            ++mp1[i];
        }
        vector<pair<int,int>> pr;
        vector<int> result;
        for(auto i = mp1.cbegin();i != mp1.cend();++i){
            pr.push_back(make_pair(i->second,i->first));
        }
        sort(pr.begin(),pr.end(),cmp);
        for(auto i = pr.cbegin();i != pr.cend();++i){
            if(k != 0){
                result.push_back(i->second);
            }
            else{
                break;
            }
            k--;
        }
        return result;
    }
};

分析：也是比较简单的一道题，通过这道题可以复习一下各种 STL数据结构，总也不用生疏了。

错误：STL有一些生疏，调了一段时间才调好。

练习

Leetcode 451

给定一个字符串 s ，根据字符出现的频率对其进行降序排序。一个字符出现的频率是它出现在字符串中的次数。返回已排序的字符串。

class Solution {
public:
    static bool cmp(pair<char,int> &a,pair<char,int> &b){
        return a.second > b.second;
    }
    string frequencySort(string s) {
        string result = "";
        map<char,int> mp;
        for(auto i : s){
            mp[i] += 1;
        }
        vector<pair<char,int>> pr;
        for(auto i = mp.cbegin();i != mp.cend();i++){
            pr.push_back(make_pair(i->first,i->second));
        }
        sort(pr.begin(),pr.end(),cmp);
        for(auto i = pr.cbegin();i != pr.cend();i++){
            for(int j=0;j<i->second;j++){
                result += i->first;
            }
        }
        return result;
    }
};

分析：桶排序的变形题，没有什么新意，还是数据结构

一遍AC

Leetcode 75

void sortColors(vector<int>& nums) {
    int n = nums.size();
    int p0 = 0;
    int p1 = 0;
    for(int i=0;i<n;++i){
        if(nums[i] == 1){
            swap(nums[i],nums[p1]);
            ++p1;
        }
        else if(nums[i] == 0){
            swap(nums[i],nums[p0]);
            if(p0 < p1){
                swap(nums[i],nums[p1]);
            }
            ++p0;
            ++p1;
        }
    }
}

分析：荷兰国旗问题，双指针一次遍历就可以得到三个数字的排序。

错误：想复杂了。

总结

排序算法基本都可以写，就是变形的题目还是有些不太熟练。还是要多多练习。