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

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))
1
2
3
4
5
6
7
8
9
10

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] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                i -= 1
            else:
                break
    return arr


n = [2, 3, 53, 2, 6, 83, 2, 4, 1, 21, 64, 4]
print(insert_sort(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.选择排序

• 原理： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 外层循环： 控制次数，相当于索引
• 内层循环： 每次从寻找的数的后边开始和当前的数对比,小了则与当前的数字索引交换

def select_sort(arr):
    for i in range(len(arr)):
        # 设置当前的索引为最小的索引
        min_num_index = i
        # 从后边未排序的数里寻找是不是有比他小的数字，有了则改为小的索引，直到把所有的数都判断完了，最后与原来数的位置进行交换
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_num_index]:
                min_num_index = j
        arr[min_num_index], arr[i] = arr[i], arr[min_num_index]
    return arr

arr = [2, 3, 1, 5, 4, 12, 46, 21, 6]
print(select_sort(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13

4.快速排序

• 思想：当拿到一个数列时候，我们拿第一个值做中间值，然后开始从列表的剩下的值开始与中间值比较，让中间值的左边都比他小，右边都比他大，因此我们 需要设置两个指针，分别指向头和尾，一个指针一个指针的开始动，例如尾指针指向的值必须比中间值小，当不符合条件时候，我们将这个值放在头指针 处，然后头指针开始运行，指向的值如果比中间值小，指针继续向后移动，当值比中间值大，将此值放入我们尾指针处，然后尾指针前移，如此反复，直到最后中间值的左边都比他小，右边都比他大，此时指针会重合，此时重合的位置就是中间值应该插入的位置
• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n^2)
  

def quick_sort(arr, first, last):
    if first >= last:
        return
    # 定义一个头指针和尾指针，分别指向最开始和最后一个数
    low, high = first, last
    # 定义一个中间值，默认我们取第一个元素
    mid_value = arr[low]
    '''
    此时low指针的值被当做中间值，那么我们让尾部指针开始动，当尾指针的数比中间值小，那么将这个值放入头指针处，头指针开始后移，
    并且开始进行头指针数的判断,如果头指针所指的数比中间值的数大，那么将这个值放到尾指针指的地方，尾指针开始前移，直到一个时刻
    头指针和尾指针恰巧都指向空，此时的位置就是中间值的位置。
    '''
    while low < high:
        '''
        判断尾指针的数是不是大于中间值，大于则符合，继续往前移动，小于则退出循环，将该值放入头指针处，但是倘若在比较的过程中，
        中间值和当前值正好相等怎么办，为了让我们相等的值全部放在一边，因此在任意一个循环加入等于该值的情况，就相当于把我们的
        中间值当成一个特殊的唯一值。
        '''
        while low < high and arr[high] >= mid_value:
            high -= 1
        arr[low] = arr[high]
        # 该值放入头指针处后，头指针开始进行判断和后移，不符合则把不符合的值放到尾指针处，并且退出循环
        while low < high and arr[low] < mid_value:
            low += 1
        arr[high] = arr[low]
    # 此时跳出循环后，low=high，因此此时的位置就是我们中间值的位置,所以我们high和low位置=中间值
    arr[low] = mid_value
    '''
    此时中间值左边都是比它小的值，右边都是大的值，我们再将左右两半的数组进行重复的排序，本来可以使用列表的特性，分为左右各
    一半的列表，但是为了不开辟新的空间，因此我们还在本列表进行操作,此时成为了递归函数，因此就需要设置递归停止的条件，只要
    当我们需要排序的数组只有一个元素时候，就可以停止，所以当first>=last时候就可以停止，因此开始的结束循环由此而来。
    '''
    quick_sort(arr, first, low - 1)
    quick_sort(arr, low + 1, last)

arr=[3,2,4,1,6,2,0,5]
quick_sort(arr,0,len(arr)-1)
print(arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

上边的排序在原列表中更改，如果使用切片特性，可以开辟新空间的话，可以修改为以下：

def quick_sort(arr):
    # 当只有一个元素时候不需要排序
    if len(arr) < 2:
        return arr
    else:
        # 定义一个中间值，一般选择第一个元素
        pivot = arr[0]
        # 把小于中间值的放在左边，大于中间值的放在右边
        small_arr = [I for I in arr[1:] if I < pivot]
        large_arr = [J for J in arr[1:] if J > pivot]
        return quick_sort(small_arr) + [pivot] + quick_sort(large_arr)


arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
print(quick_sort(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.归并排序

• 思想： 对两个已经做好排序的数组（相同排序规则）A和B，通过分治法把其合并到一个有序数组C（依次从两个数组中取元素比较然后放进C中即可。而如果A、B数组都只有一个元素时，他们都成为了一个有序数组，则可以直接进行比较放在数组C中，返回有序的数组C。）。
• 分治法：
  通过分治思想对无序数组排序问题进行划分：对于一个无序的数组arr
  （1）分解：通过递归将无序数组进行划分，每次从arr的len//2处划分为两个数组，直到划分后的子数组规模为1。
  （2）解决：当子数组规模为1时，此时的最小规模数组已经自动变为一个有序数组，递归终止返回有序数组结果。
  （3）合并：接收下一层递归所返回的两个有序子数组，将这两个有序子数组的数据进行合并为一个新的有序数组，然后返回该有序数组给上一层递归。
• 图片实例：为方便理解递归划分数组，可以建立一个递归树形图（理解递归比较方便）。以数组arr =[3,23,4,13,4,5,63,6,2]为例，其数组划分树形图:
  从最下层依次排序，汇总到上一层，循环直到第一层全部排序完。
• 时间复杂度：无特殊情况，只有O(log2n)
• 博主学习链接：https://www.bilibili.com/video/BV1ZW411q7vG?p=1

# 将数组对折拆分，然后再拆分，继续拆分到每组只要两个，将此两个大小排好，和另一组再大小排好，直到都排好
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    # 按照len//2拆分,递归函数内部会一直拆分，直到长度为1不拆分
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    
	# 设置指针
    left_pivot, right_pivot = 0, 0
    result = []  # 归并排序需要设置返回值
    
    # 开始进行交换，当有一方游标的列表交换完，将另一半的列表直接放入，因为已经排好序
    while left_pivot < len(left_arr) and right_pivot < len(right_arr):
        # 将小的先放入列表,并且指针加一
        if left_arr[left_pivot] < right_arr[right_pivot]:
            result.append(left_arr[left_pivot])
            left_pivot += 1
        else:
            result.append(right_arr[right_pivot])
            right_pivot += 1
    # 当循环出来的时候，一定是一方的指针已经遍历完自己的列表，只需把另一半列表放入，但是不知道是哪个列表，因此都写
    result.extend(left_arr[left_pivot:])
    result.extend(right_arr[right_pivot:])
    return result

a=[2,1,4,6,3,5]
print(merge_sort(a))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29