蓝桥杯丨简单排序_蓝桥杯排序题

做你想做的，错的算我的

这里是Want595，欢迎光临我的世界 ~

目录

前言 

一、简单排序

1、插入排序

2、选择排序

3、冒泡排序

二、问题引入

三、总结

文章目录

---

本文主要引入算法概念，介绍简单的排序算法，主要有插入排序、选择排序以及冒泡排序

一、简单排序

1、插入排序

插入排序，顾名思义，每次在待排序序列中挑选一个，插入已有序序列中，该算法是个稳定的算法。

插入排序的过程如下：

 插入排序的算法描述如下：

#插入排序
lst=list(map(int,input().split(',')))      （1）
for i in range(1,len(lst)):                （2）
   for j in range(i):                      （3）
        if lst[j]>lst[i]:                  （4）
            t=lst[i]
            lst.pop(i)
            lst.insert(j,t)
            break
lst

算法分析如下： 

（1）输入一行整数，放入一个列表中，作为待排序序列

（2）第一重循环，遍历待排序序列，一个个插入到有序序列中

（3）第二重循环，遍历已排序序列（已排序序列为第一个元素到第i-1个元素），目的是找到待插入元素的位置，执行插入排序操作

（4）当待插入的位置找到后，将元素插入有序序列时不要忘记在在原序列将其删除

注：这里的有序序列与待排序序列是相对的，其实都是一个序列，相当于对序列进行原地排序

2、选择排序

选择排序，意思是每次在待排序序列中寻找一个最小值（或者最大值）放入到有序序列中，该算法是个不稳定的算法。

选择排序的过程如下：

选择排序的算法描述如下：

#选择排序
lst=list(map(int,input().split(',')))             （1）
for i in range(len(lst)):                         （2）
    minindex=i                                    （3）
    for j in range(i,len(lst)):                   
        if lst[minindex]>lst[j]:                  
            minindex=j
    lst[i],lst[minindex]=lst[minindex],lst[i]     （4）
lst

算法分析如下： 

（1）输入待排序序列，放入列表中

（2）第一重循环，遍历待排序序列

（3）第二重循环，每次寻找待排序序列中的最小值，保存其下标

（4）每次将最小值放到已有序序列的最后面

3、冒泡排序

冒泡排序的意思是：从待排序序列中依次比较，如果前一个元素大于后一个元素，就交换两者的位置，冒泡排序每一趟会把待排序序列中最大或最小的元素最终位置确定下来，该算法是个稳定的算法。

冒泡排序的过程如下：

 

冒泡排序的算法描述如下：

#冒泡排序
lst=list(map(int,input().split(',')))           （1）
for i in range(len(lst),0,-1):                  （2）
    flag=0                                      （3）
    for j in range(i-1):
        if lst[j]>lst[j+1]:
            lst[j],lst[j+1]=lst[j+1],lst[j]
            flag=1
    if flag==0:                                 （4）
        break
lst

算没分析如下： 

（1）输入一行整数，放入列表中，作为待排序序列

（2）从列表最后一个元素开始向前遍历，方便冒泡排序

（3）设置一个标志，若发生交换，则置1，未发生交换，则置0

（4）当不发生交换时，可以提前结束循环 

二、问题引入

给定n个数，并按从小到大的顺序，以列表的形式输出这n个数中前m小的数

输入格式：第一行输入两个数n和m，第二行输入n个数

输出形式：输出一个列表

保证数据范围1<=m<=n<=10^6

样例输入：

4 2

6 2 5 3 

分析：首先用插入排序对列表进行排序，然后用列表切割的方法获取前m个元素即可  

n,m=map(int,input().split(' '))
lst=list(map(int,input().split(' ')))
for i in range(1,len(lst)):
    for j in range(i):
        if lst[j]>lst[i]:
            t=lst[i]
            lst.pop(i)
            lst.insert(j,t)
            break
lst[0:m]

三、总结

本文主要介绍了三种最基本的排序算法，其中，选择排序是个不稳定的算法，插入排序与冒泡排序都是稳定的排序算法。

文章目录