排序算法比较

bash
| 排序算法 | 最好时间复杂度    | 最坏时间复杂度    | 平均时间复杂度         | 空间复杂度    | 是否稳定  | 核心思想            |
| ---- | ---------- | ---------- | --------------- | -------- | ----- | --------------- |
| 冒泡排序 | O(n)       | O(n²)      | O(n²)           | O(1)     | ✅ 稳定  | 相邻比较，大的冒后面      |
| 选择排序 | O(n²)      | O(n²)      | O(n²)           | O(1)     | ❌ 不稳定 | 每轮选最小，放前面       |
| 插入排序 | O(n)       | O(n²)      | O(n²)           | O(1)     | ✅ 稳定  | 当前元素插入已排好序列     |
| 快速排序 | O(n log n) | O(n²)      | O(n log n)      | O(log n) | ❌ 不稳定 | 分治 + 找基准 + 左右排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n)      | O(n)     | ✅ 稳定  | 分治 + 合并有序子序列    |
| 希尔排序 | O(n log n) | O(n²)      | O(n^1.3)\~O(n²) | O(1)     | ❌ 不稳定 | 插入排序的优化（分组）     |
| 堆排序  | O(n log n) | O(n log n) | O(n log n)      | O(1)     | ❌ 不稳定 | 构建大顶堆/小顶堆       |
| 计数排序 | O(n + k)   | O(n + k)   | O(n + k)        | O(n + k) | ✅ 稳定  | 用数组记录频次         |
| 桶排序  | O(n + k)   | O(n²)      | O(n + k)        | O(n + k) | ✅ 稳定  | 分桶 + 各桶分别排序     |
| 基数排序 | O(nk)      | O(nk)      | O(nk)           | O(n + k) | ✅ 稳定  | 按位排序（从低到高）      |

python自带排序

Python 默认的排序使用的是 Timsort（提姆排序） 算法，

Timsort = Merge Sort（归并排序） + Insertion Sort（插入排序） 的优化组合

bash
| 特性          | 说明                       |
| ----------- | ------------------------ |
| **稳定排序**    | 相等元素顺序不变 ✅               |
| **时间复杂度**   | 最好 O(n)，平均/最坏 O(n log n) |
| **空间复杂度**   | O(n) 辅助空间                |
| **优化小数组**   | 小段用插入排序                  |
| **优化已排序数据** | 已部分有序数据时性能更好（比快速排序快）     |

冒泡排序

思路：

bash
相邻元素比较，把大的交换到后面

每轮把最大值“冒泡”到末尾

bash
>> def bubble_sort(lst: list) -> list:
...     """冒泡排序
...     exam:
...         origin: [10, 8, 9, 6]
...         思路：相邻比较，大的往后放
...         第一轮：
...         first: [8, 10, 9, 6]
...         second: [8, 9, 10, 6]
...         third: [8, 9, 6, 10]
...         第二轮： [9, 6, 10]依次思路去比较
...         ...
...     """
...     n = len(lst)
...     # 外层控制轮数
...     for i in range(n):
...         # 内层控制相邻比较次数
...         for j in range(0, n-i-1):
...             if lst[j] > lst[j+1]:
...                 lst[j], lst[j+1] = lst[j+1], lst[j]    

简单优化：加入交换标记，如果一轮下来啥都没有交换，默认已经为交换完成，后续不需要再比较

bash
>>> def bubble_sort(lst: list) -> list:
...     """冒泡排序
...     exam:
...         origin: [10, 8, 9, 6]
...         思路：相邻比较，大的往后放
...         第一轮：
...         first: [8, 10, 9, 6]
...         second: [8, 9, 10, 6]
...         third: [8, 9, 6, 10]
...         第二轮： [9, 6, 10]依次思路去比较
...         ...
...     """
...     n = len(lst)
...     # 外层控制轮数
...     for i in range(n):
...         swapper = False  # 标记是否有交换
...         # 内层控制相邻比较次数
...         for j in range(0, n-i-1):
...             if lst[j] > lst[j+1]:
...                 lst[j], lst[j+1] = lst[j+1], lst[j]    
...                 swapper = True
...         if not swapper:
...             break

插入排序

思路：

bash
当前元素插入到左边已排序序列中

类似打扑克牌理牌

bash
>>> def insertion_sort(arr: list):
...     """插入排序： 当前元素插入到左边已排序序列中
...     将第一个元素看作已排序部分
...     从第二个元素开始，向前找到它应插入的位置
...     插入后，前 i 个元素就是有序的
...     重复直到最后一个元素
...     """
...     for i in range(1, len(arr)):
...         key = arr[i]
...         j = i - 1
...         # 向左比较并移动元素
...         while j>=0 and arr[j] > key:
...             arr[j + 1] = arr[j]
...             j -= 1
...         arr[j + 1] = key
... 
>>> arr = [7, 3, 5, 2]
>>> insertion_sort(arr)
>>> arr
[2, 3, 5, 7]

快排

思路：每轮通过基准值，分拆成3块，比基准值小的部分，基准值，比基准值大的部分，再依次对基准值小的部分、大的部分，做类似的分拆，直到剩1个值或为空时返回（这里之所以必须要小于等于1，是因为如果以2个值为基准时，这两个是可能乱序，只剩1个或0个，则返回必然是有序的）

例子：[3,1,2,5,6,7]

• 1、借助递归思路，最外层递归实现为return [1,2] + [3] + [5,6,7]
• 2、再往里一层left_lst=[1,2]则是由[] + [1] + [2]
• 3、同层right_lst=[5,6,7]则是由[] + [5] + [6,7]，这里的[6,7]则是由继续再往里一层递归返回[6,7]=[] + [6] + [7]

**时间复杂度：**O(n*n)，平均时间复杂度为O(nlogn)

bash
def quickSorted(lst):

    #base
    if len(lst) <= 1:
        return lst

    pivot = lst[0]#基准值

    left_lst = quickSorted([item for item in lst[1:] if item<pivot])
    right_lst = quickSorted([item for item in lst[1:] if item>=pivot])
    return left_lst + [pivot] + right_lst

归并排序

bash
>>> def merge_sort(lst: list) -> list:
...     """分解（Divide）：
... 
... 把数组从中间分成两半
... 
... 对每一半递归进行归并排序
... 
... 解决（Conquer）：
... 
... 每次递归到长度为 1，认为是有序的
... 
... 合并（Merge）：
... 
... 把两个有序子数组合并成一个有序大数组"""
...     if len(lst) <= 1:
...         return lst
...     # half
...     mid = len(lst) // 2
...     left = merge_sort(lst[:mid])
...     right = merge_sort(lst[mid:])
...     # merge
...     return merge(left, right)
... 
>>> def merge(left: list, right: list) -> list:
...     result = []
...     i = j  = 0  # 左右指针，分别指向left right列表
...     # 比较左右两边元素大小，依次放入result
...     while i<len(left) and j<len(right):
...         if left[i] <= right[j]:
...             result.append(left[i])
...             i += 1
...         else:
...             result.append(right[j])
...             j += 1
...     # 把还没比较完的一边剩下的元素，直接拼到结果中
...     # 每次从 left[i] 和 right[j] 中挑一个小的加到 result，直到其中一个数组先走完（全部添加完）
...     # 注意：其中一个一定是空的，所以最多只会添加一边的剩余部分
...     result.extend(left[i:])  # 如果 left 剩下元素，就全加进来
...     result.extend(right[j:])  # 如果 right 剩下元素，就全加进来
...     return result
... 
>>> lst = [1,7,3,9,2,1,5,6]
>>> merge_sort(lst)
[1, 1, 2, 3, 5, 6, 7, 9]