选择、冒泡、归并排序

简单选择排序

def select_sort(items, comp=lambda x, y: x < y):

    items = items[:]
    for i in range(len(items) - 1):
        min_index = i
        for j in range(i + 1, len(items)):
            if comp(items[j], items[min_index]):
                min_index = j
        items[i], items[min_index] = items[min_index], items[i]
        print('items---->', items)
    return items

冒泡排序

def bubble_sort(items, comp=lambda x, y: x > y):

    items = items[:]
    for i in range(len(items) - 1):

        for j in range(len(items) - 1 - i):
            if comp(items[j], items[j + 1]):
                print('items[j], items[j + 1]', items[j], items[j + 1])
                items[j], items[j + 1] = items[j + 1], items[j]
        print('items---->', items)
        print('')
    return items

归并排序

def merge(items1, items2, comp=lambda x, y: x < y):
    """合并(将两个有序的列表合并成一个有序的列表)"""
    items = []
    index1, index2 = 0, 0
    while index1 < len(items1) and index2 < len(items2):
        if comp(items1[index1], items2[index2]):
            items.append(items1[index1])
            index1 += 1
        else:
            items.append(items2[index2])
            index2 += 1
    items += items1[index1:]
    items += items2[index2:]
    print('----->', items)
    print('')
    return items

def merge_sort(items, comp=lambda x, y: x < y):
    return _merge_sort(list(items), comp)

# 归并排序
def _merge_sort(items, comp):

    if len(items) < 2:
        return items
    mid = len(items) // 2
    left = _merge_sort(items[:mid], comp)
    right = _merge_sort(items[mid:], comp)
    print('left--->', left)
    print('right--->', right)
    return merge(left, right, comp)

if __name__ == '__main__':
    print(select_sort([8, 4, 5, 7, 1, 3, 6, 2]))
    # print(bubble_sort([8, 4, 5, 7, 1, 3, 6, 2]))
    # print(merge_sort([8, 4, 5, 7, 1, 3, 6, 2, 9]))

备注

冒泡排序：
时间复杂度：O(n²)
空间复杂度：O(1)，只需要一个额外空间用于交换
稳定性：冒泡排序是稳定的排序算法，因为可以实现值相等的元素的相对位置不变，例如我们上面的代码中，if comp(items[j], items[j + 1]):items[j], items[j + 1] = items[j + 1], items[j] ,只有当items[j]> items[j+1]的时候才交换，这时候就是稳定的，假如写成if (items[j]>= items[j+1]) { swap(arr, j, j + 1); },冒泡排序的功能还是可以实现，但是值相等的元素的相对位置发生了改变，此时就是不稳定的。

　　归并排序
　　归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。空间复杂度为n+logn

本文地址：https://blog.csdn.net/weixin_44715081/article/details/110876495