| 时间复杂度 | 名称 | 示例算法 |
|---|---|---|
| O(1) | 常数时间复杂度 | 哈希表查找 |
| O(logn) | 对数时间复杂度 | 二分查找 |
| O(n) | 线性时间复杂度 | 遍历数组 |
| O(nlogn) | 线性对数时间复杂度 | 快速排序 |
| O(n^2) | 平方时间复杂度 | 冒泡排序、插入排序 |
| O(n^3) | 立方时间复杂度 | 矩阵乘法 |
| O(2^n) | 指数时间复杂度 | 穷举搜索 |
| O(n!) | 阶乘时间复杂度 | 旅行商问题 |
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)一、快速排序
快速排序（Quick Sort）是一种基于分治思想的排序算法，是目前使用最广泛的排序算法之一。其基本思想是选取一个基准元素，然后将数组分成小于等于基准的子数组和大于基准的子数组，再递归地对这两个子数组进行快速排序，最后将它们合并起来即可。
二、快速排序步骤
快速排序： 的核心操作是分割数组操作
划分操作采用两种方式：Lomuto 分割和 Hoare 分割。
- Lomuto 分割比较简单，但是在特定情况下会导致快速排序的时间复杂度退化为 O(n^2)
- Hoare 分割较为复杂，但是效率更高，通常被认为是优化后的快速排序算法 nlong
复杂度 最坏复杂度 n^2 平均复杂度 nlong 递归复杂度 nlong
快速排序的基本步骤：
- 选取数组中的一个元素作为基准元素（通常是数组的第一个元素）。
- 将数组中比基准元素小的元素移动到数组的左边，将比基准元素大的元素移动到数组的右边。
- 对左右两边的数组分别重复上述操作，直到所有数组都有序为止。
选择数组第一位元素位基准值，创建两个新数组，分别存放小于基准值和大于基准值的元素然后这两个新数组递归进行上述操作(再选新数组，再分组)，直到数组为空然后将左右数组和基准值进行拼接三、应用例子
def quicksort(arr):# 如果数组长度小于等于1，则直接返回该数组if len(arr) <= 1:return arrelse:# 选择第一个元素作为基准pivot = arr[0]# 构造小于等于基准的元素构成的子数组 less构造大于基准的元素构成的子数组 greaterless = [x for x in arr[1:] if x <= pivot]# 输出比第一个元素小的列表greater = [x for x in arr[1:] if x > pivot]# 输出比第一个元素大的列表print('less-----------', less)print('greater-----------', greater)# 递归地对这两个子数组进行快速排序，然后将它们合并起来，并加上基准元素return quicksort(less) + [pivot] + quicksort(greater)if __name__ == '__main__':arr = [3, 5, 2, 8, 1, 4]sorted_arr = quicksort(arr)print(sorted_arr)选择基准元素：从待排序数组中选择一个元素作为基准（通常选择第一个元素）分割数组：重新排列数组，将所有小于基准的元素放在基准的左边，所有大于基准的元素放在基准的右边，等于基准的元素可以放在任意一边。此时，基准元素的位置也已经确定递归排序：递归地对基准元素左边的子数组和右边的子数组进行快速排序合并结果：将左边子数组、基准元素、右边子数组依次拼接起来，得到排好序的数组