基础算法

1.插入排序
2.冒泡排序
3.选择排序
4.归并排序
5.快速排序

应用场景

离散化

先将数组排序,然后进行去重,排序后的数组进行二分查找返回下标,元素位于的下标位置就是第几大元素.所以离散化数组初始化一开始一般会加个0,或者从1开始存入数据 AcWing 121. 赶牛入圈

int get(int x)
{
    int l=0;r=nums.size();
    while(l<r)
    {
        int mid=(l+r)>>1
        if(nums[mid]>=x)    r=mid;
        else l=mid+1
    }
    return r;
}

nums.push_back(0);  //初始化
for(int i=0;i<n;i++)
{
    cin>>g[i];
    nums.push_back(g[i]);
}
sort(nums.begin(),nums.end())
nums.erase(unique(nums.begin(),nums.end()),nums.end())
for(int i=0)
{
    int pos=get(nums[i]);
    nums[pos]=g[i];//依据题目而定
}

转化为中位数问题

中位数的特点:所有点到中位数的距离之和最小
最基础的应用就是直接利用上述性质,无需转化就可以将题目转化为到同一个点的距离AcWing 104. 货仓选址
通常这种性质都是放在最后求不同的值减去同一个值的和的最小值使用
经典问题就是环形均分纸牌问题(隐藏条件:当交换次数最小的时候一定有两个人之间没有进行纸牌交换)

环形纸牌传递的板子题 AcWing 122. 糖果传递

二维环形纸牌传递 AcWing 105. 七夕祭

环形均分纸牌问题(二维的把每一行或者每一列看成整体的思想值得借鉴)

• 求平均数
• 减去平均数求前缀和
• 排序找前缀和的中位数
• 求所有abs(前缀和减去中位数)的和

普通均分纸牌问题

• 求平均数
• 减去平均数求前缀和
• 求所有前缀和的前缀和(abs)

堆排序的应用(等到数据结构篇再具体更新)

找第K大的元素

动态选取中位数

优先级队列

逆序对数目的计算

冒泡排序

冒泡排序中每次交换就代表着一个逆序对被消灭,所以开一个变量cnt,在交换的时候++最后打印cnt就可以了

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

归并排序

归并排序找逆序对的思想很重要,当一个问题可以分治成左半边,右半边,左半边某个和右半边某个的问题时这种思想就很重要,因为在判断第三种情况的时候,通常需要用到有序的性质,而归并排序就能在处理问题的同时对数组进行有序处理,就省去了每次递归调用时候的排序问题(因此在进行排序的时候应该根据解题需求来处理) AcWing 119. 袭击

//这个是在排序的时候就进行了解决题目需求的处理,而袭击需要排序之后
class Solution {
public:
    int res=0;
    int inversePairs(vector<int>& nums) {
        if(nums.size()==0)    return 0;
        else mergesort(nums,0,nums.size()-1);
        return res;
    }
    void mergesort(vector<int>& nums,int l,int r)
    {
        if(l>=r)
            return;
        vector<int> temp;
        int mid=(l+r)>>1;
        mergesort(nums,l,mid);
        mergesort(nums,mid+1,r);
        int i=l;
        int j=mid+1;
        while(i<=mid&&j<=r)
        {
            if(nums[i]<nums[j]) temp.push_back(nums[i++]);
            else
            {
                temp.push_back(nums[j++]);
                res+=mid-i+1;
            }
        }
        while(i<=mid) temp.push_back(nums[i++]);;
        while(j<=r) temp.push_back(nums[j++]);
        int k=0;
        for(int i=l;i<=r;i++)
        {
            nums[i]=temp[k++];

        }
    }
};