力扣-排序算法

排序算法，一般都可以使用std：：sort（）来快速排序。

这里介绍一些相关的算法，巩固记忆。

快速排序

跟二分查找有一丢丢像。

首先选择一个基准元素，一般就直接选择第一个。然后两个指针，一个指向第一个，一个指向最后一个。第一个现在是空，就从最后一个开始，跟基准元素做判断，小于基准元素的就放到第一个位置，然后第一指针往后移。按这种顺序直到两个指针相遇，相遇的位置放入基准元素。然后从基准元素劈开两半，再按相同方法排序。

void quicksort(vector<int> nums,int l,int r){
    if(l+1>=r)
        return;
    int first=l,last=r-1;
    int 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;
    quicksort(nums,l,first);
    quicksort(nums,first+1,r);
}

归并算法

归并算法是一种分治算法，先分再治。比如说8个数字。先分成4个4个，然后4个内部再继续分，分成2个2个。2个排好序后合并，4个排好序后再合并。

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

插入排序

首先是一个数，本来就有序。接着两个数进行排序。接着三个数。

所谓插入，比如说八个数进行排序，其实前七个已经有序，这个时候只需要把第八个插入到前七个数的合适位置即可。怎么插入，就从后往前，一个一个比较，如果小于就往前移。

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

冒泡排序

相邻两个数比较，大的往后移，每一轮最大的数将会移到最后。

可以进行一个优化，可能出现一种情况，从第二轮过后，其实数组已经是有序的了，但是按照算法步骤来走的话，即使已经排好序了，但仍是会进行后边的比较，知道全部比较完成

因此，我们可以对代码进行优化，如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。

解决方式：可以通过一个标志位来进行判断

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

选择排序

选择最小的数跟第一个数交换，按照同样的方法对后面的n-1个进行排序。

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

215.数组中的第K个元素

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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4输出: 4

提示：

• 1 <= k <= nums.length <=
•  <= nums[i] <=

题解

可以利用快速排序的思想来解决这个问题。

选择一个数，然后将大于它的数字往后移，小于的往前移。如果这个刚好是第k位，直接返回。如果不是，大于k，则对前面做相同的排序，如果不是就对后面做相似的排序。这里的k指的是第k大，因此从小到大排就是第n-k位。

class Solution {
public:
    int quickselect(vector<int> &nums,int l,int r,int k){
        if(l==r)
            return nums[k];
        int p=nums[l],i=l-1,j=r+1;
        while(i<j){
            do i++; while (nums[i] < p);
            do j--; while (nums[j] > p);
            if(i<j)
                swap(nums[i],nums[j]);
        }
        if(k<=j) 
            return quickselect(nums,l,j,k);
        else 
            return quickselect(nums,j+1,r,k);
    }
    int findKthLargest(vector<int> &nums, int k) {
        int n=nums.size();
        return quickselect(nums,0,n-1,n-k);
    }
};

347.前k个高频元素

347. 前 K 个高频元素

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <=
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

题解

可以使用桶排序，使用STL库中的unordered_map，提供了一种基于哈希表的键值对容器。

可以对每一个数字出现的次数进行计算并且存储。

    unordered_map<int,int> m;
        for(int num:nums) m[num]++;

接着进行排序，然后再定义一个新的数组用来存储要返回的数组。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        for(int num:nums) m[num]++;
        vector<pair<int,int>> s;
        for(auto t:m)
            s.push_back({t.second,t.first});
        sort(s.begin(),s.end());
        vector<int> ans;
        int t=s.size()-1;
        while(k--){
            ans.push_back(s[t--].second);
        }
        return ans;
    }
};

排序这里也有一个库可以使用。

<priority_queue> 是标准模板库（STL）的一部分，用于实现优先队列。

优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        for(int num:nums) m[num]++;
        priority_queue<pair<int,int>> s;
        for(auto i:m) s.emplace(i.second,i.first);
        vector<int> ans;
        while(k--){
            ans.push_back(s.top().second);
            s.pop();
        }
        return ans;
    }
};

不得不说如果熟悉使用STL库，真的省事很多。