三傻排序（冒泡，选择，插入）

今天第一天搞点简单的

文章目录

• 前言
• 一 冒泡排序
• 二 选择排序
• 三 插入排序

前言

今天先搞点简单的，后面会逐渐增加难度，也是我自己的一个复习进度

一、冒泡排序

本质上就是n-1轮循环

然后每一轮把最大的数换到右边去，下一轮就少处理一个数

换的方法就是挨着比较第一个和第二个比，大的话就到右边，第二个和第三个比大的话就到右边。这样不管怎么样大的都会到右边

//冒泡排序
#include <bits/stdc++.h>
using namespace std;
const int M1=100;
int x[M1];
int n;
int main() {
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i];
}//输入n个数
for (int i=n-1;i>=1;i–)//最多进行n-1轮
{
for(int j=1;j<=i;j++) //每一轮冒泡可以确定一个最大的数
{
if(x[j]>x[j+1])
{
swap(x[j],x[j+1]);
}
}
}
for(int i=1;i<=n;i++)
{
cout<<x[i]<<" ";
}
}

二 选择排序

就是每一轮选一个第i小的数排在第i位

//选择排序
#include <bits/stdc++.h>
using namespace std;
const int M1=100;
int x[M1];
int n;
int main() {
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i];
}//输入n个数
for(int i=1;i<=n;i++)
{
int ans=i;//最小值的下标
for(int j=i;j<=n;j++)
{
if(x[j]<=x[ans])//找[i,n]的最小值，比较后更新下标
{
ans=j;
}

}
swap(x[i],x[ans]);//将小的值放在最前面的位置
/**
注意这里i=1时找的是整个数组的最小值，i=2时找的是第二小的值；
**/
}
for(int i=1;i<=n;i++)
{
cout<<x[i]<<" ";
}
return 0;
}

三 插入排序

从[1,1]开始，排[1，2]如果遇到当前数比前面的数小，就一直往左移动，一直到它前面的数比它小为止这样每一个都是有序的，一直到[1,n]

//插入排序
//两个条件，1.左边没数了，停止。2.左边的比右边的小，停止
#include <bits/stdc++.h>
using namespace std;
const int M1=100;
int x[M1];
int n;
int main() {
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i];
}//输入n个数
for(int i=1;i<=n;i++)//对区间[1，i]进行排序
{
for(int j=i;j>=1;j–)
{
if(j==1||x[j-1]<=x[j])//条件
{
break;
}
else
{
swap(x[j-1],x[j]);
}
}
}
for(int i=1;i<=n;i++)
{
cout<<x[i]<<" ";
}
}