冒泡排序
算法思想
- 每次将最大的一下一下地运到最右边，然后确定这个最大的，接着可以发现该问题变成一个更小的子问题。
- 具体操作：从左向右扫描，如a[i]>a[i+1]，执行swap操作。
- 代码格式
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N];
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
//i表示当前要确定的位置
for(int i=n;i>=1;i--)
{
for(int j=0;j<i-1;j++) // 修改这里，将范围改为从0到i-1
{
if(a[j]>a[j+1])swap(a[j],a[j+1]);
}
}
//输出
for(int i=0;i<n;i++)cout<<a[i]<<(i==n?"\n":" ");
return 0;
}
- 时间复杂度为平方级，所以适用于数字比较少的情况。
选择排序
选择排序的思想
- 与冒泡排序的区别是每次找出最大的放在最右边。
- 具体操作：
计算出最大元素的下标，max_id,执行swap操作swap(a[max_id],a[i])
实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N];
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
//i表示当前要确定的位置
for(int i=n-1;i>=0;i--)
{
int max_id=0;
for(int j=0;j<=i;j++)
{
if(a[j]>a[max_id])max_id=j;
}
swap(a[max_id],a[i]);
}
//输出
for(int i=0;i<n;i++)cout<<a[i]<<(i==n-1?"\n":" "); // 修改这里，将条件改为i==n-1
return 0;
}
例题讲解
- 上述代码改成从大到小排序：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N];
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
//i表示当前要确定的位置
for(int i=0;i<n-1;i++)
{
int max_id=i;
for(int j=i+1;j<n;j++)
{
if(a[j]>a[max_id])max_id=j;
}
swap(a[i],a[max_id]);
}
//输出
for(int i=0;i<n;i++)cout<<a[i]<<(i==n-1?"\n":" "); // 修改这里，将条件改为i==n-1
return 0;
}
插入排序
思想
- 将待排序的序列依次插入到已排序的序列之中。
实现
//i表示当前要确定的位置
for(int i=2;i<=n;++i)
{
//此时[1,i-1]已经为有序数组
int val=a[i],j;
//将val和j比较，如果小于就往后移动，为val腾出位置
for(j=i;j>1&&val<a[j-1];--j)
{
a[j]=a[j-1];
}
//此时j为给val腾出的位置
a[j]=val;
}
实现解释：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
这段代码中的变量i表示当前要确定的位置，val表示当前要插入的值，j用于在已排序的数组中寻找插入的位置。在每次循环中，都会将val和j-1位置的元素进行比较，如果val小于a[j-1]，则将a[j-1]向后移动一位，为val腾出位置。当找到合适的位置后，将val插入到该位置
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int a[N];
int main()
{
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
//i表示当前要确定的位置
for(int i=2;i<=n;++i)
{
//此时[1,i-1]已经为有序数组
int val=a[i],j;
//将val和j比较，如果小于就往后移动，为val腾出位置
for(j=i;j>1&&val<a[j-1];--j)
{
a[j]=a[j-1];
}
//此时j为给val腾出的位置
a[j]=val;
}
for(int i=1;i<=n;++i)cout<<a[i]<<" ";
return 0;
}
归并排序
思想
- 将一个数组
- 实现：将一个数组分成两个子数组，将子数组再向下递归的排序直至元素个数为1。然后将相邻的元素合并起来。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N],b[N];
//归并排序的算法
void MerageSort(int a[],int l,int r)
{
//1.递归出口：左右边界相等
if(l==r)return ;
//2.取mid
int mid=(l+r)/2;
//3.递归排序：左右两个区间分别排序
MerageSort(a,l,mid);
MerageSort(a,mid+1,r);
//4.设置指针
int pl=l;int pr=mid+1;int pb=l;
//5.两个指针合法，开始循环
while(pl<=mid||pr<=r)
{
if(pl>mid)
{
//左半边已经放完
b[pb++]=a[pr++];
}
else if(pr>r)
{
//右半边已经放完
b[pb++]=a[pl++];
}
else
{
//两边都还有元素，取最小值放到b数组中
if(a[pl]<a[pr])b[pb++]=a[pl++];
else b[pb++]=a[pr++];
}
}
//完成后要把b数组复制回去a数组
for(int i=l;i<=r;++i)a[i]=b[i];
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
MerageSort(a,1,n);
for(int i=1;i<=n;++i)cout<<a[i]<<(1==n?"\n":" ");
return 0;
}
快速排序
思想
快速排序是一种分治法的排序方法，原理是将一个数组分成两个子数组，其中一个子数组的所有元素都小于另一个子数组的元素，然后递归的对这两个子数组进行排序。
时间复杂度为O(nlogn),且不需要额外的空间。
实现
void QuickSort(int a[],int l,int r)
{
if(l<r)
{
int mid=Partition(a,l,r);
QuickSort(a,l,mid-1);
QuickSort(a,mid+1,r);
}
}
int Partition(int a[],int l,int r)
{
int pivot=a[r];//设a[r]为基准，这一次partition会将a[r]放到正确的位置上
int i=l,int j=r;//设置两个下标，分别往中间走
while(i<j)
{
while(i<j&&a[i]<=pivot)i++;//左边的小于基准，不需要交换，继续往中间走
while(i<j&&a[j]>=pivot)j--;
if(i<j)swap(a[i],a[j]);
else swap(a[i],a[r]);
}
return i;
}
- 完整版宝藏排序：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N];
int Partition(int a[],int l,int r)
{
int pivot=a[r];//设a[r]为基准，这一次partition会将a[r]放到正确的位置上
int i=l;int j=r;//设置两个下标，分别往中间走
while(i<j)
{
while(i<j&&a[i]<=pivot)i++;//左边的小于基准，不需要交换，继续往中间走
while(i<j&&a[j]>=pivot)j--;
if(i<j)swap(a[i],a[j]);
else swap(a[i],a[r]);
}
return i;
}
void QuickSort(int a[],int l,int r)
{
if(l<r)
{
int mid=Partition(a,l,r);
QuickSort(a,l,mid-1);
QuickSort(a,mid+1,r);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
QuickSort(a,1,n);
for(int i=1;i<=n;++i)cout<<a[i]<<(i==n?"\n":" ");
return 0;
}
桶排序
思想
分类+分治。
把元素的值域分为若干段，每一段对应一个 桶。
操作
- 将值域分为若干段，每一段对应一个桶。
- 每个元素放在对应的桶中。
- 对每个桶分别排序。
- 按顺序把每个桶中的元素依次取出，合并成最终答案。
实现
- 每个桶放一个元素
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
int a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
int x;
cin >> x;
a[x]++;
}
for(int i = 0; i <= n; i++)
for(int j = 0; j < a[i]; j++) {
cout << i << ' ';
}
return 0;
}
- 每个桶是一段区间
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
vector<int>a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
int x;
cin >> x;
a[x/1000].push_back(x);
}
for(int i = 0; i <N; i++) //对每一个桶进行排序
{
sort(a+1,a+n+1);
}
for(int i=0;i<N;i++)
{
for(auto item:a[i])
{
cout<<item<<" ";
}
}
cout<<endl;
return 0;
}
此时的时间复杂度为：每个桶排序的时间复杂度之和。
优势
- 适用于数据量比较大，但是值域比较小。
- 一个值 对应一个桶的情况的时间复杂度为O（n），此时很推荐使用桶排序。
例题
#include<bits/stdc++.h>
using namespace std;
int n,perc;
int bucket[607];
int main()
{
cin>>n>>perc;//输入成绩及获奖百分比
for(int i=1;i<=n;i++)
{
int x,sum=0;
cin>>x;
bucket[x]++;//将新成绩放入对应的桶中
for(int j=600;j>=0;j--)//从小到大枚举 每一个桶
{
sum+=bucket[j];//统计当前成绩的个数
if(sum>=max(1,perc*i/100))
{
cout<<j<<" ";
break;//如果当前人数大于等于获奖比例，那么此时的分数线就为当前分数
}
}
}
}
未完待续，大家一起加油吧！！
![[OpenCV学习笔记]Qt+OpenCV实现图像灰度反转、对数变换和伽马变换](https://img-blog.csdnimg.cn/direct/fc1224c2f0b84a49b017689ffa02763a.gif#pic_center)
![[已解决]Vue3+Element-plus使用el-dialog对话框无法显示](https://img-blog.csdnimg.cn/direct/3c03ad7e96624a7eb00ae1f7a1a4d288.png)
![报错[Vue warn]: $listeners is readonly. $attrs is readonly.怎么解决？](https://img-blog.csdnimg.cn/direct/d76d079c6d8f4b078ae68ac9fdf39ac0.png)
