排序算法
这里先写几种排序算法
排序算法，经典的几种排序算法，就那么几个，如下：
- 冒泡排序
- 插入排序
- 选择排序
- 归并排序
- 快速排序
这一篇，先讲一些原地排序算法，就是前三种。
冒泡排序
冒泡排序只会操作相邻的两个数据，每次都是比较这2个，然后根据条件去互换，一次冒泡至少让一个元素移动到它应该在的位置，重复N次，就完成了工作。
重点来了：
- 它是原地排序算法
- 它是稳定的排序算法
- 时间复杂度O(n^2)
代码Python
from typing import List def bubble_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(length): made_swap = False for j in range(length - i - 1): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] made_swap = True if not made_swap: break
插入排序
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
重点来了：
- 它是原地排序算法
- 它是稳定的排序算法
- 时间复杂度O(n^2)
代码Python
def insertion_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(1, length): value = a[i] j = i - 1 while j >= 0 and a[j] > value: a[j + 1] = a[j] j -= 1 a[j + 1] = value
选择排序
选择排序（英语：Selection sort）是一种简单直观的排序算法。它的工作原理是每次找出第 i 小的元素（也就是 A_{i..n} 中最小的元素），然后将这个元素与数组第 i 个位置上的元素交换。
重点来了：
- 它是原地排序算法
- 它是不稳定的排序算法
- 时间复杂度O(n^2)
代码Python
def selection_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(length): min_index = i min_val = a[i] for j in range(i, length): if a[j] < min_val: min_val = a[j] min_index = j a[i], a[min_index] = a[min_index], a[i]
小结
稳定的排序算法
这三种算法，整体上来说都是原地排序算法；其次，算法时间复杂度都是O(n^2)。比较耗时间。下次，去看下其他的算法，像归并，快排，都是经常用的，特别是快排。其实快排挺好玩的，还用到了一些好玩的概念，一点一点来。
说明：我只是用python写了这几种算法代码，如果有需要其他的，我可以补充上来。毕竟，学习算法只是为了熟悉算法流程，语言不重要，思想逻辑挺重要的。如果有喜欢其他语言的，我可以提供出来相关语言代码的实现。
