python– 简单的排序

1. 冒泡排序
--> 两两比较,交换位置
--> 属交换排序
-->  n个数从左至右，编号从0开始到n-1，索引0和1的值比较，如果索引0的值大，则交换两者位置，如
果索引1大，则不交换。继续比较索引1和2的值，将大值放在右侧。直至n-2和n-1比较完，第
一轮比较完成。第二轮从索引0比较到n-2，因为最右侧n-1位置上已经是最大值了。依次类推，
每一轮都会减少最右侧的不参与比较，直至剩下最后2个数比较 
 
冒泡排序方法(一)
lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    for j in range(length-1-i):   
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
print(lst)
第四行, length-1-i,为什么要减i呢? 
    因为每次比较过程,都可以确定出当前这轮的极值(极大),并且放置在最右端,形成一个有序区域. 
    不减i也不会影响最终比较结果,只是做了一些无用的比较
如果列表内是字符串,上面代码依然适用.因为'>' '<' 可用于同类型比较,(不同类型的比较,需要设定key的类型)
上面代码的时间复杂度为O(n**2),优化点,如果某一轮比较过程中并没有交换发生,意味着序列已经排好

冒泡排序方法(二)
lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    flag = False
    for j in range(length-1-i):
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
            flag = True
    if not flag:
        break
print(lst)

红色部分为方法一二的区别,用标记辅助排序,记录此轮比较是否有交换发生, 如果没有发生交换,排序结束

总结

冒泡法需要数据一轮轮比较

最好的情况是,初始顺序是最终的期望,遍历n-1次

最差的情况是,初始顺序与期望相反,遍历n(n-1)/2

用标记记录此轮是否有交换发生,如果没有发生交换,排序结束

时间复杂度为O(n**2)

2. 简单选择排序

–> 两两比较,找极值

–> n个数从左至右，索引从0开始到n-1，两两依次比较，记录大值索引，此轮所有数比较完毕，将
大数和索引0数交换，如果大数就是索引1，不交换。第二轮，从1开始比较，找到最大值，将它
和索引1位置交换，如果它就在索引1位置则不交换。依次类推，每次左边都会固定下一个大数(降序排列)。

简单排序实现(一)

lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    maxindex = i                 # 默认迭代值i对应的值为最大值
    for j in range(i+1,length):
        if lst[maxindex] < lst[j]:
            maxindex = j
    if i != maxindex:           # 避免两数相等的情况(相邻数字大小相等,不交换位置)
        lst[i], lst[maxindex] = lst[maxindex], lst[i]
print(lst)

总结
-> 需要数据一轮轮比较，并在每一轮中发现极值
-> 没有办法知道当前轮是否已经达到排序要求，但是可以知道极值是否在目标索引位置上
-> 遍历次数n(n-1)/2
-> 时间复杂度O(n2)


3. 插入排序
-> 在前端增加哨兵位置,构建有序区域,迭代无序区数据和有序区的数据做比较运算

-> 增加一个哨兵位,每轮放入待比较数
哨兵依次和待比较的前一个数据比较,大数靠右移动,找到哨兵 (中的值的位置) 位置插入
每一轮结束后,得到一个从开始到待比较数位置的一个有序序列

插入排序实现(一)
lst = [1,9,8,5,6,7,4,3,10]
num1 = [0] + lst               # 列表前补0,做哨兵位
length = len(num1)
for i in range(2,length):      # 索引0为哨兵,1位有序区
    num1[0] = num1[i]
    j = i - 1                  # j为有序区边界(极大)值索引
    if num1[j] > num1[0]:      # 大数右移,找到可插入位置(当前哨兵值)
        while num1[j] > num1[0]:
            num1[j+1] = num1[j] # 依次右移
            j -= 1
        num1[j+1] = num1[0]    # 将哨兵插入, 注意插入在右侧要 +1
print(num1)
print(num1[1:])

~~~~~~~~~~~~~~~~~以下为函数输出~~~~~~~~~~~
[10, 1, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 3, 4, 5, 6, 7, 8, 9, 10]

问题1, 为什么需要执行 num1[j+1] = num1[0].
触发该行操作的条件是, 待比较数小于哨兵,那么就在该数的下一个索引位置插入哨兵
问题2, 输出num1列表为什么会多出数字10.
10在原列表中索引为-1,最后一次比较中,10不大于哨兵10,循环结束,初始哨兵位的0已被10覆盖,所以列表num1第一个元素为10


选择排序还需要继续啃,还是有优化点值得学习的.