排序算法集合

冒泡排序

一般情况下，冒泡排序都是来两次大循环就能排好序，但是在要求性能的情况下，也是可以优化的，避免很多无用的循环遍历。

有两个优化点：

• 大部分已经有序了，设置剩余无序的边界
• 全部有序了，退出循环，结束

def bubble_sort(data_list):
    # 时间复杂度最大的情况下需要循环的次数
    run_cnt = len(data_list)

    # 初始化最后一次交换数据的位置，如果没有交换的话说明后面的已经是有序的了，
    # 避免了下一次大循环中再做无用功
    last_exchange_index = 0

    # 初始化循环的边界值，默认是到最后一个
    sortborder = run_cnt - 1

    for i in range(run_cnt):
        # 初始化整个序列为有序，如果发生了交换，说明是无序的，继续循环排序
        isSorted = True
        for j in range(sortborder):
            if data_list[j] > data_list[j + 1]:
                data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j]
                # 发生了交换，设置为false，继续遍历
                isSorted = False
                # 发生了交换，设置最后一次的交换位置
                last_exchange_index = j
                
        # 将最后一次的交换位置赋值给循环的边界，下一次的排序，只需要比较到边界处即可
        sortborder = last_exchange_index
        
        # 如果在这一次的排序过程中没有发生数据交换，则说明整个序列已经排好序了，可以直接退出
        if isSorted:
            break


data_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(data_list)
print(data_list)

# 避免重复无用排序的isSorted测试用例
# 【5, 8, 6, 3, 9, 2, 1, 7】

# 无序边界测试last_exchange_index用例
# [3, 4, 2, 1, 5, 6, 7, 8]

快速排序

遍历队列，每次找到最大或最小的元素，放到队列的首端或尾端。

def quick_sort(data_list):
    run_cnt = len(data_list)

    for i in range(run_cnt - 1):
        min_index = i
        for j in range(i+1, run_cnt):
            min_index = j if data_list[j] < data_list[min_index] else min_index
        data_list[min_index], data_list[i] = data_list[i], data_list[min_index]


data_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(data_list)
print(data_list)