蓝桥之手撕排序算法——冒泡、选择、插入、快排、归并(Python版)

1. 排序引言

2. 冒泡排序

2.1 算法思想

2.2 代码实现

2.3 时空复杂度分析

3. 选择排序

3.1 算法思想

3.2 代码实现

3.3 时空复杂度分析

4. 插入排序

4.1 算法思想

4.3 代码实现

4.4 时空复杂度分析

5. 快速排序

5.1 算法思想

5.2 代码实现

5.3 时空复杂度分析

6. 归并排序

6.1 算法思想

6.2 代码实现

6.3 时空复杂度分析

1. 排序引言

排序算法是算法竞赛中的第一入门必会的算法，可能在语言里面内置好sort排序函数，但是在排序算法中的很多思想是值得我们去学习的，比如从快速排序里面学会如何进行分治以及递归的实现。

2. 冒泡排序

冒泡排序是学习语言和算法中必会的一种算法，下面就由我来进行冒泡排序的分析与代码实现：

2.1 算法思想

对于一个无序数组，我们从索引0开始往右对比，如果当前数字比后一个数字大，就进行交换。

这样每次就可以将最大的放在最右边，上一次对比的最右边的就不再参与下一次排序

因为有N个数，每一次可以将一个最大数排好序，最后一个数也就定好了，因此只需要N-1次，就能排好完整的序。

我们可以看看以下的图：

其实到这里，冒泡排序算法就已经很明确了，每次冒泡都能求出当前最大的数，并将其放在最右边。

2.2 代码实现

a = [6, 5, 4, 1, 3, 2]
n = len(a)
for i in range(n - 1):for j in range(n - i - 1):if a[j] > a[j + 1]:a[j], a[j + 1] = a[j + 1], a[j]
print(a)

2.3 时空复杂度分析

时间复杂度：

每次需要比较进行n - i - 1次，也就是n - 1 、 n - 2 、 n - 3.....1次

一共要执行n - 1次，大概估算也就是O（n²）

空间复杂度：

在原数组上面进行的操作，并没有开辟新的空间，所以为：O(1)

3. 选择排序

3.1 算法思想

每次从左往右开始找，找到最小的，然后与当前的索引的数进行交换，并索引加一

这样就能保证，每次都将最小的数排在最前面了。

3.2 代码实现

a = [6, 5, 4, 1, 3, 2]
n = len(a)
for i in range(n - 1):minn = a[i]index = ifor j in range(i + 1, n):if a[j] < minn:minn = min(minn, a[j])index = ja[i], a[index] = a[index], a[i]
print(a)

3.3 时空复杂度分析

时间复杂度：

每一次都要从左往右开始比较，从n - 1 次到1次，也就是n(n - 1) / 2次

一共要进行n - 1次，所以时间复杂度为：O(n²)

空间复杂度：

没有开辟额外空间，为：O(1)

4. 插入排序

4.1 算法思想

还是从左往右开始进行排序，当前这个数与前面的每一个数进行比较，如果当前的数比前一个数小，那么就一直往左边走，直到那个数比当前的数大为止。

到当前这个数的时候，前面的数其实已经排序好了，只需要找个合适的位置插入进行就好了。

4.3 代码实现

a = [6, 5, 4, 1, 3, 2 , 10]
n = len(a)
for i in range(1 , n):now = a[i]index = ifor j in range(i - 1 , -1 , -1):if a[j] > now:index = ja[j + 1] = a[j]else:breaka[index] = now
print(a)

4.4 时空复杂度分析

时间复杂度：

插入排序比选择排序更加优化一点，但是最坏情况都是O(n²)

但是最好的情况下（已经有序），只需要O(n)就行了

空间复杂度：

没有开辟额外的数组，O(1)

5. 快速排序

5.1 算法思想

快速排序是基于分治算法实现的

分治：将一个大问题分解为多个小问题，分别解决这些小问题，然后将它们的解合并起来，从而得到大问题的解。通常，分治算法包含三个步骤：分解（Divide）、解决（Conquer）、合并（Combine）。

要想理解分治，首先得理解什么是递归？

递归：递归是指在解决问题的过程中调用自身的过程。在编程中，递归是一种常见的编程技巧，它通过将问题分解成更小的、类似的子问题来解决复杂的问题。

这是一个简单的递归函数：

def factorial(n):# 基本情况if n == 0:return 1# 递归情况return n * factorial(n - 1)

不难发现，其实这就是求解阶乘的函数，f(n) = n * fn(n - 1)，直到计算到最底层f(0) = 1 ，也就是0的阶乘，然后再不停地返回值，最终得到n的阶乘

当然，上面不理解的话，我们先可以看一下他的实现逻辑：

先进行分解，算到最底层之后，又从下面往上面推，最终算出f(4)的结果为24

了解什么是分治和递归之后，我们就可以开始愉快的快速排序啦~

快速排序基本步骤：

在数组中找一个基准值x，一般是中间那个值
将数组分成两个部分：1. 小于等于x的那部分， 2. 大于x的那部分
对两边递归使用该策略

最重要的步骤其实是将数组分成两个部分：

设置基准值l
存放小于等于基准值的下标为：idx = l + 1
从l + 1到r 遍历
- 如果当前的a[i]<=l , a[i] , a[idx]互换，并且idx += 1
最后就交换idx - 1和 l (idx是刚好大于l的，所以要-1，因为前面执行过一次idx += 1)，就能保证l的左边是小于等于基准值的，右边是大于基准值的

5.2 代码实现

a = [6, 5, 4, 1, 3, 2, 10]
n = len(a)def fn(a, l, r):# 基准值为：lidx = l + 1   # 右边的索引for i in range(l + 1, r + 1):# 将小于基准值的方在左边 ，大于基准值的放在右边if a[i] <= a[l]:a[i], a[idx] = a[idx], a[i]idx += 1# 将基准值放在中间a[idx - 1], a[l] = a[l], a[idx - 1]# 返回基准值的位置return idx - 1def quick_sort(a, l, r):if l > r:returnmid = fn(a, l, r)  # 分基准值为l，分成两部分，左边<=mid ， 右边>midquick_sort(a, l, mid - 1)   # 对左边处理quick_sort(a, mid + 1, r)   # 对右边处理quick_sort(a, 0, n - 1)
print(a)

5.3 时空复杂度分析

时间复杂度：

在一般情况下，我们每次需要遍历分成两个部分，需要执行n次，每次都分成两个部分，相比线性时间，每次排序的都少了一半，于是就是Logn次

总时间复杂度大概在O(n * logn)

空间复杂度：

每次递归都是一次递归二叉树，消费的栈空间大概在O(logn)

6. 归并排序

6.1 算法思想

归并排序也是基于分治算法来的

只是归并排序是先递归，再进行合并

算法步骤：

先分成两个部分
每部分都处理成有序的
再将两个数组合并起来

6.2 代码实现

a = [6, 5, 4, 1, 3, 2, 10]
n = len(a)def merge(a,b):res = []while len(a) != 0 and len(b)!=0:if a[0] <= b[0]:    # 将小的值先放入resres.append(a.pop(0))else:res.append(b.pop(0))# 将a,b剩下的值放进来res.extend(a)res.extend(b)return resdef merge_sort(a):if len(a) < 2:return amid  = len(a) // 2  # 每次分为两个部分left = merge_sort(a[:mid])   # 对左边处理right = merge_sort(a[mid:])   # 对右边处理return merge(left , right)   # 合并两部分a = merge_sort(a)
print(a)