排序算法1
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。概括：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序、快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。
希尔排序线性阶 (O(n)) 排序，基数排序，此外还有桶、箱排序。
关于稳定性
排序后 2 个相等键值的顺序和排序之前它们的顺序相同。
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释
n：数据规模
k：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
先从蓝桥一道算法题切入
蓝桥题库3225
测试输入
5
1 5 9 3 7
测试输出
1 3 5 7 9
1、冒泡排序
冒泡排序是一种通过不断比较和交换相邻元素来将数列按升序排列的简单算法。其名称源自于较小元素会逐渐“浮”到数列顶部的过程。尽管冒泡排序易于理解和实现，但它的效率较低，尤其是对大数据集。为了提高效率，可以引入一个标志变量（flag），如果在一次完整的遍历中没有发生任何交换，则表明数列已经有序，从而提前结束排序过程。这种优化虽然能在一定程度上减少不必要的比较次数，但对于整体性能的提升并不显著。
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。（执行n-1轮）
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
Python 代码
n = int(input())
li = list(map(int,input().split()))
# 冒泡排序
# 执行n-1轮
for i in range(1,n):
# 第i次从a[0]到a[n-i-1] 列表下标从0开始
for j in range(n-i):
# 每一次循环选出第i大的数，升序，冒出当前最大的泡泡
if li[j]>li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
print(' '.join(map(str,li)))
通过输入样例，从每轮的结果来看看冒泡排序
n = int(input())
'''
5
1 5 9 3 7'''
li = list(map(int,input().split()))
# 冒泡排序
# 执行n-1轮
for i in range(1,n):
# 第i次从a[0]到a[n-i-1] 列表下标从0开始
for j in range(n-i):
# 每一次循环选出第i大的数，升序，冒出当前最大的泡泡
if li[j]>li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
# 看得更直观，打印每轮的结果
print(li)
print(' '.join(map(str,li)))
2、选择排序
选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是每次从未排序的部分中选出最小（或最大）的元素，放到已排序部分的末尾。尽管选择排序的时间复杂度为 O(n²)，在数据规模较小时仍有一定的应用价值，因为它不占用额外的内存空间。
算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
Python 代码
n = int(input())
li = list(map(int,input().split()))
# 选择排序
for i in range(n-1):
# 以升序为例，第i次从a[i]到a[n-1]找最小元素放到序列最前面
# i从0开始，每次找第i小的数
min_value = li[i]
min_idx = i
# 往后遍历未排序部分，
for j in range(i,n):
if li[j] < min_value:
# 更新min_value
min_value = li[j]
min_idx = j
# 此时，a[min_idx]更新成为 每次比较都是相邻的两个比
li[i],li[min_idx] = li[min_idx],li[i]
print(' '.join(map(str,li)))
3、插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，其基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，打过扑克牌的话，可以类比一下我们刚拿到手牌时顺牌的情景。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入，这里要结合二分去理解。
算法步骤
将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从后往前依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
Python 代码
n = int(input())
li = list(map(int,input().split()))
# 插入排序
# 对于第i个数字，在区间[0,i-1]中 从后往前 找对应插入的位置
for i in range(1,n):
# 抽出来的元素 对应提到的占用额外空间O(1)
value = li[i]
# 插入元素的下标 一开始默认li[1]和li[0]去比，选出li[0]的合适人选
insert_idx = 0
for j in range(i-1,-1,-1):
# 如果遍历到的li[j]大于value，就把li[j]往后挪一位
# 注意是从后往前排，从后往前找
if li[j]>value:
li[j+1] = li[j]
else:
# 找到合适的位置
insert_idx = j+1
break
# 插入第i个数字到已排序数组中
li[insert_idx] = value
print(' '.join(map(str,li)))
