从零开始备战蓝桥杯——一天一个小算法第一天（排序篇）

今天使我们学习算法的第一天，算法内容为冒泡排序和选择排序。

冒泡排序

思想：

两两相邻数字排序，小的放在前面大的放在后面。

从左往右遍历，不断重复第一步，这样可以永远保证大的在最后面

重复上述操作，可以得到一个数组从小到大的排序。

事例：

假设我们有n个数字。

第一次比较遍历全部数字，进行两两比较，小的在前，大的在后，最后最大的数字排在最后数第二的位置。

循环往复，直至全部。

时间复杂度为o（n^2） 空间复杂度为o（1）

python代码如下：

n=int(input())#多少数字
a=list(map(int,input().split()))#读取整型数字为列表。
for i in range(1,n):
    for j in range(n-i):#第一次遍历全部数字，往后逐渐减小，因为n个数字最大的下标为n-1所以i要从1开始
        if a[j]>a[j+1]:
            a[j],a[j+1]=a[j+1],a[j]#如果前面的数字大于后面的数字则交换顺序。
print(a)

 c++代码如下:

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e3+1;
int a[N];//一千以内的数组排序
int main()
{
  int n;cin>>n;
  for(int i =0;i<n;i++)cin>>a[i];
  for(int i =1;i<n;i++)
  {
    for(int j=0;j<n-i;j++)
    {
      if(a[j]>a[j+1])
      {
        swap(a[j],a[j+1]);//交换两数位置。
      }
    }
  } 
  for (int i = 0; i < n; i++)cout << a[i]<<" ";
    return 0;
}

 学会冒泡排序，就去蓝桥官网用刚学会的排序做到题目试一下吧。

蓝桥账户中心https://www.lanqiao.cn/problems/3225/learning/?page=1&first_category_id=1&problem_id=3225

随后我们来学习选择排序。

选择排序

思想：

选择排序与冒泡排序相似，可以找出最小的数字或则最大的数字放在最前面或最后面。

首先从左往右选择最小的元素放在第一个位置。

之后选择第二小的元素放在第二个位置。

重复上述操作，依次找到最小，第二小，第三小......。

事例：

假设我们有n个数字。

首先从[0，n-1]找到最小的数字，放在第一位。

随后从[1,n-1]中找到第二小的数字，放在第二位。

再从[2,n-1]中找到第三小的数字，放在第三位。

循环往复，直至全部。

时间复杂度为 o(n^2）空间复杂度为o（1）

python代码如下：

n=int(input())#多少数字
a=list(map(int,input().split()))
for i in range(n-1):
    min_number=a[i]#先定义最小的数字为第a[i]
    min_idx=i#定义该数字的下标为i
    for j in range(i,n):
        if a[j]<min_number:
            min_number=a[j]记录最小数字
            min_idx=j#记录最小数字位置
    a[i],a[min_idx]=a[min_idx],a[i]#将a[i]与最小的数字换位置。
print(a)

c++代码如下：

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e3+1;
int a[N];//一千以内的数字
int main()
{
  int n;cin>>n;
  for(int i =0;i<n;i++)cin>>a[i];
  for(int i =0;i<n-1;i++)
  {
    int min_number=a[i];
    int min_ind=i;//定义一个位置
    for(int j=i;j<n;j++)
    {
      if(a[j]<min_number) 
      {
        min_number=a[j];
        min_ind=j;//将位置定义为更小数的下标
      }
    }
    swap(a[i],a[min_ind]);
  } 
  for (int i = 0; i < n; i++)cout << a[i]<<" ";
    return 0;
}

学会了选择排序，快试一下用选择排序解决排序问题吧。

蓝桥云课选择排序题

OK今天的算法内容就到这了，今天是学算法的第一天，算法最重要的内容是要多练，你的放弃可能会成就更多的人，我们明天再见。