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

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] < 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)) 

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)) 

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) 

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

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)) 

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))