【编程算法Ⅱ】冒泡排序、选择排序、插入排序（Python解法）

给你一个n代表有n个数字，给出这n个数字，然后你需要使用冒泡排序将这些数字从小到大排好。

冒泡排序只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)；最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，因此最好情况时间复杂度是O(n)；最坏的情况是，排序的数据刚好是倒序排列，我们需要进行n次冒泡操作，因此最坏情况时间复杂度为O(n2)；因为时间复杂度考虑最坏情况，因此冒泡排序时间复杂度是O(n2)

①输入元素赋值；

②一层遍历列表中的元素，二层遍历一层元素未排序的元素，因此j取(n-i-1)，lis[j]和lis[j+1]相比，将每次最大的元素置换到能到达的最后位置；

③逻辑：首先列表中最大元素被置换到最后一位，列表中第二大元素被置换到最后第二位……打印输出lis。

n = int(input())
lis = list(map(int,input().split(' ')))
for i in range(n):
    for j in range(n-i-1):
        if lis[j] > lis[j+1]:
            lis[j],lis[j+1] = lis[j+1],lis[j]
print(' '.join(map(str,lis)))#给lis中的元素定义字符串，才能安全输出

给你一个n代表有n个数字，然后你需要使用选择排序将这些数字从小到大排好。

冒泡排序的时间复杂度也为O(n2)，它将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。然后每次会 从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

①输入元素赋值；

②一层遍历列表中的元素，minindex(最小元素位置)初始值为i，二层遍历一层未排序区的元素，将minindex替换为未排序区最小元素的位置，二层遍历结束后，将i位置元素值和minindex位置元素值替换，继续一层遍历；

③打印输出lis。

n = int(input())
lis = list(map(int,input().split(' ')))
for i in range(n):
    minindex = i
    for j in range(i+1,n):
        if lis[minindex] > lis[j]:
            minindex = j
    lis[i],lis[minindex]=lis[minindex],lis[i]
print(' '.join(map(str,lis)))

给你一个n代表有n个数字，然后你需要使用插入排序将这些数字从小到大排好。

插入排序的时间复杂度也为O(n2)，和选择排序类似，插入排序也将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，然后每次加载未排序区间的第一个元素，放入已排序区重新排列，直至结束。

①输入元素赋值；

②一层遍历列表中的元素，二层倒序遍历已排序区的元素，将新加载的元素替换到正确的位置；

③打印输出lis。

n = int(input())
lis = list(map(int,input().split(' ')))
for i in range(n):
    for j in range(i,0,-1):#倒序
        if lis[j] < lis[j-1]:
            lis[j-1],lis[j]=lis[j],lis[j-1]
print(' '.join(map(str,lis)))

大家如果有疑问都可以评论提出，有不足之处请大家批评指正，希望能多结识这方面的朋友，共同学习、共同进步。