[数据结构与算法]排序算法及稳定性

一、冒泡排序

1、冒泡排序，从前往后，两两进行比较，最大的放在最后面
2、稳定
3、时间复杂度o(n^2) 最优是不排序o(n)

# 排序算法
# 1、冒泡排序，从前往后，两两进行比较，最大的放在最后面
# 2、稳定
# 3、时间复杂度o(n^2) 最优是不排序o(n)
def bubble(lst):
    n = len(lst)
    for i in range(n-1): # 只需要遍历前n-1个元素
        for j in range(n-i-1): # 从0-n-1,从1-n-2
            if lst[j] > lst[j+1]: # 这里i控制起始的位置，j控制两两比较移动的位置
                lst[j], lst[j + 1] = lst[j+1], lst[j] # 如果出现前面的比后面大，就交换，继续到下一个遍历
    return lst
lst = bubble([3,2,14,6])
print(lst)

二、选择排序

1、选择排序，从未排序的列表中选择最小的向已排序的列表中插入
2、不稳定 5 8 5 2

# 选择排序
# 从未排序的列表中选择最小的向已排序的列表中插入
# 不稳定  5 8 5 2
def select(nums):
    n = len(nums)
    for i in range(n-1):
        minindex = i
        for j in range(i+1, n):
            if nums[minindex] > nums[j]:
                minindex = j
        if i != minindex:
            nums[minindex], nums[i] = nums[i], nums[minindex]
    return nums
lst = select([2, 1, 5, 3, 6, 9, 4])
print(lst)

插入排序

1、插入排序，从未排序的列表中向已排序的列表中插入元素,确定当前索引j，然后与已排序的列表一一对比，最终交换使得变为排序好的列表
2、稳定的 [5, 5, 2]

# 插入排序
# 从未排序的列表中向已排序的列表中插入元素,确定当前索引j，然后与已排序的列表一一对比，最终交换使得变为排序好的列表
# 稳定 [5, 5, 2]
def insert(nums):
    n = len(nums)
    for i in range(1, n): # 从第二个开始遍历
        j = i
        while j > 0:
            if nums[j] < nums[j-1]: # 如果后面的比前面的小
                nums[j], nums[j-1] = nums[j-1], nums[j] # 交换
                j -= 1
            else: # 如果后面的比前面的大，直接退出循环
                break
    return nums
lst = insert([5, 5, 2])
print(lst)