常见的排序算法及其时间复杂度

0.常见排序算法的时间和空间复杂度

1.冒泡排序

• 思想：：每次将最大的浮出去
• 内层循环：作用是将一个最大的数浮出外边，两两比较，比如十个数，两两比较再交换，无论交不交换比较需要经历10-1次，就是len-1
• 外层循环：作用是浮出的次数，例如十个数，第一次浮出一个，剩下的九个长度再浮出去，浮出一个又剩8个浮出去，总共需要len-1每次都-1，直到都浮出去
• 时间复杂度：最坏时间复杂度O(n^2)，最好O(n)

def bubble_sort(li):
    for j in range(len(li) - 1):  # 将所有的数字冒泡
        for i in range(len(li) - 1):  # 冒泡一个数需要更换len(li)-1
            if li[i] > li[i + 1]:
                li[i], li[i + 1] = li[i + 1], li[i]
    return li


n = [2, 3, 53, 2, 6, 83, 2, 4, 1, 21, 64, 4]
print(bubble_sort(n))

2.插入排序

• 思想： 每拿到一个数，去前边排好序的数里找自己的位置，插入到属于他的位置
• 外层循环： 相当于索引，从1开始是因为第一个数不需要插入，最后一个数的索引是len-1
• 内层while循环： 负责判断前边的数和当前的数的大小,当小于前边的数则需要交换，并且自己的索引-1，再和前边的判断，不符合则跳出循环
• 时间复杂度：O(n^2)

def insert_sort(arr):
	#第一个数不需要插入
    for i in range(1, len(arr)):
    	# 当前数和前边的数比大小，小则交换，大则结束循环
        while i > 0:
            if arr[i]