关于python:十一Python排序-冒泡排序直接排序简单选择排序

1.冒泡排序

冒泡排序是一种替换排序。
什么是替换排序呢？
替换排序：两两比拟待排序的关键字，并替换不满足秩序要求的那对数，直到整个表都满足秩序要求为止。

代码示例：

def bubble_sort(demo:list):
    length = len(demo)
    for i in range(length):
        print("*"*30)
        for j  in range(length-i-1):
            if demo[j] > demo[j+1]:
                demo[j],demo[j+1] = demo[j+1], demo[j]
        print('{}次:'.format(i),demo)
    print("最终排序：",demo)

if __name__ == '__main__':
    num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
    bubble_sort(num_list)

后果：

******************************
0次: [4, 15, 2, 33, 57, 9, 52, 72, 55, 90]
******************************
1次: [4, 2, 15, 33, 9, 52, 57, 55, 72, 90]
******************************
2次: [2, 4, 15, 9, 33, 52, 55, 57, 72, 90]
******************************
3次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
4次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
5次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
6次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
7次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
8次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
9次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
最终排序： [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]

从后果中看出，其实在第3次时，就曾经实现了排序，之后的迭代只是在浪费时间，所以能够优化下。
代码示例：

def bubble_sort(demo:list):
    flag = False
    length = len(demo)
    for i in range(length):
        print("*"*30)
        for j  in range(length-i-1):
            flag = False
            if demo[j] > demo[j+1]:
                demo[j],demo[j+1] = demo[j+1], demo[j]
                flag = True
        print('{}次:'.format(i), demo)
        if not flag:
            break

    print("最终排序：",demo)
    

if __name__ == '__main__':
    num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
    bubble_sort(num_list)

后果

******************************
1次: [4, 2, 15, 33, 9, 52, 57, 55, 72, 90]
******************************
2次: [2, 4, 15, 9, 33, 52, 55, 57, 72, 90]
******************************
3次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
最终排序： [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]

2.间接排序

原理：
在未排序序列中，构建一个子排序序列，直至全副数据排序实现。
将待排序的数，插入到曾经排序的序列中适合的地位。
减少一个哨兵，放入待比拟值，让它和前面曾经排序好的序列比拟，找到适合的插入点。

代码示例

def direct_insert_sort(demo):
    print('排序前{}'.format(demo))
    demo = [0] + demo
    length = len(demo)
    for i in range(2, length):
        demo[0] = demo[i]  # 搁置哨兵
        j = i - 1
        if demo[j] > demo[0]:
            while demo[j] > demo[0]:
                demo[j+1] = demo[j]
                j -= 1
            demo[j + 1] = demo[0]
        print('{}次:{}'.format(i, demo))
    demo = demo[1:]
    print("最终排序{}".format(demo))



if __name__ == '__main__':
    num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
    direct_insert_sort(num_list)

后果:

排序前[33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
2次:[4, 4, 33, 15, 2, 72, 57, 9, 52, 90, 55]
3次:[15, 4, 15, 33, 2, 72, 57, 9, 52, 90, 55]
4次:[2, 2, 4, 15, 33, 72, 57, 9, 52, 90, 55]
5次:[72, 2, 4, 15, 33, 72, 57, 9, 52, 90, 55]
6次:[57, 2, 4, 15, 33, 57, 72, 9, 52, 90, 55]
7次:[9, 2, 4, 9, 15, 33, 57, 72, 52, 90, 55]
8次:[52, 2, 4, 9, 15, 33, 52, 57, 72, 90, 55]
9次:[90, 2, 4, 9, 15, 33, 52, 57, 72, 90, 55]
10次:[55, 2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
最终排序[2, 4, 9, 15, 33, 52, 55, 57, 72, 90]

3.简略抉择排序

简略抉择排序是一种抉择排序。
抉择排序：每趟从待排序的记录中选出关键字最小的记录，程序放在已排序的记录序列开端，直到全副排序完结为止。

代码示例

def simple_select_sort1(demo:list):
    """
    简略抉择排序
    :param demo:
    :return:
    """
    length = len(demo)
    for i in range(length):
        maxindex = i
        for j in range(i + 1, length):
            if demo[maxindex] < demo[j]:
                maxindex = j
        if i != maxindex:
            demo[i], demo[maxindex] = demo[maxindex], demo[i]
        print("{}次{}".format(i, demo))
    print("最终排序".format(demo))

def simple_select_sort2(demo:list):
    """
    优化后简略抉择排序
    :param demo:
    :return:
    """
    length = len(demo)
    for i in range(length // 2):
        maxindex = i
        minindex = -i - 1
        minorgin = minindex

        for j in range(i + 1, length - i):
            if demo[maxindex] < demo[j]:
                maxindex = j
            if demo[minindex] > demo[-j - 1]:
                minindex = -j - 1

        if i != maxindex:
            demo[i], demo[maxindex] = demo[maxindex], demo[i]
            if i == length + minindex:
                minindex = maxindex
        if minorgin != minindex:
            demo[minorgin], demo[minindex] = demo[minindex], demo[minorgin]
        print("{}次{}".format(i, demo))
    print("最终排序{}".format(demo))


if __name__ == '__main__':
    num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
    simple_select_sort1(num_list)
    print("*" * 40)
    simple_select_sort2(num_list)

后果

0次[90, 4, 15, 2, 72, 57, 9, 52, 33, 55]
1次[90, 72, 15, 2, 4, 57, 9, 52, 33, 55]
2次[90, 72, 57, 2, 4, 15, 9, 52, 33, 55]
3次[90, 72, 57, 55, 4, 15, 9, 52, 33, 2]
4次[90, 72, 57, 55, 52, 15, 9, 4, 33, 2]
5次[90, 72, 57, 55, 52, 33, 9, 4, 15, 2]
6次[90, 72, 57, 55, 52, 33, 15, 4, 9, 2]
7次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
8次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
9次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
最终排序
****************************************
0次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
1次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
2次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
3次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
4次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
最终排序[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]