蓝桥杯备赛必看：六大经典排序算法详解与代码实现
创作时间:
作者:
@小白创作中心
蓝桥杯备赛必看：六大经典排序算法详解与代码实现
引用
CSDN
1.
https://m.blog.csdn.net/Yhvaely/article/details/137057156
排序算法是计算机科学中的基础算法之一，广泛应用于数据处理和算法竞赛中。本文详细介绍了六种常见的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序和桶排序。每种算法都配有详细的原理说明和代码实现，适合正在准备蓝桥杯等编程竞赛的选手阅读。
冒泡排序
算法思想
- 每次将最大的一下一下地运到最右边，然后确定这个最大的，接着可以发现该问题变成一个更小的子问题。
- 具体操作：从左向右扫描，如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;//如果当前人数大于等于获奖比例，那么此时的分数线就为当前分数
}
}
}
}
未完待续，大家一起加油吧！！
热门推荐
一贯钱相当于现在多少钱？了解一贯钱的现代价值
生化诊断中腺苷脱氨酶的检测意义
FRM 考试内容剖析：一二级内容介绍！
现场｜美术馆里的露营篝火：有数字火焰，也有音乐演出
黄精种子播种的关键技巧，干货满满，赶紧收藏！
一路向“新” 豫立潮头 ——2024河南经济大盘点
API的10种收费模式详解：从按使用量到按数据存储量收费
弧长和扇形面积
韩遂归顺曹操：东汉末年军阀的抉择
电子驾照：方便出行的新选择
肺结节的三个误区及肺射频消融术治疗指南
如何进行笔迹鉴定
又一批城市将启用机动车电子行驶证，电子版和纸质版有不同作用
羊角蜜甜瓜种植方法和管理
离婚之后心平气和了怎么办
中耳炎多发于儿童，家长不要掉以轻心，这几种情况都是中耳炎的早期信号
WiFi 6 与 WiFi 5 对比，哪个更好？
鹤山：多举措推动传统产业转型升级 助力县域经济高质量发展
如何组织团队的增员活动
白衣焕新秘籍：让你的白色衣物重绽光芒
奥巴马：从肯尼亚之子到美国首位非裔总统
差示扫描量热仪（DSC）：材料科学中的热分析利器
羊角蜜甜瓜种植方法和管理
如何依规提取杭州省的公积金？这种提取规定有哪些具体细节？
商业银行是如何创造货币的？
男子高铁上抽根烟致列车降速被民警拘留，与朋友的旅行也泡了汤
解读影视中纪晓岚与历史纪晓岚的差异
人老腿先老，60岁后留意6个下肢疾病信号，做好4点保护下肢健康
汽车遥控器使用指南：功能介绍与操作注意事项
冬春季如何防控非洲猪瘟？技术指导来了→