评价维度
- 运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（即时间复杂度中的常数项降低）。对于大数据量情况，运行效率显得尤为重要。
- 就地性：顾名思义，「原地排序」通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
- 稳定性：「稳定排序」在完成排序后，相等元素在数组中的相对顺序不发生改变。
- 自适应性：「自适应排序」的时间复杂度会受输入数据的影响，即最佳、最差、平均时间复杂度并不完全相等。
- 是否基于比较：「基于比较的排序」依赖于比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为𝑂(𝑛 log 𝑛) 。而「非比较排序」不使用比较运算符，时间复杂度可达𝑂(𝑛) ，但其通用性相对较差。
选择排序
工作原理
「选择排序 selection sort」的工作原理非常直接：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。设数组的长度为 𝑛 ，选择排序的算法流程如图 11‑2 所示。
- 初始状态下，所有元素未排序，即未排序（索引）区间为[0, 𝑛 − 1] 。
- 选取区间[0, 𝑛 − 1]中的最小元素，将其与索引0处元素交换。完成后，数组前 1 个元素已排序。
- 选取区间[1, 𝑛 − 1]中的最小元素，将其与索引1处元素交换。完成后，数组前 2 个元素已排序。
- 以此类推。经过𝑛 − 1轮选择与交换后，数组前𝑛 − 1个元素已排序。
- 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。
代码
def select_sort(lst): size = len(lst) for i in range(size): min = i for j in range(i, size): if lst[min] >= lst[j]: min = j lst[min], lst[i] = lst[i], lst[min] return lst
算法特性
- 时间复杂度为 𝑂(𝑛2 )、非自适应排序：外循环共𝑛 − 1轮，第一轮的未排序区间长度为𝑛，最后一轮的未排序区间长度为2 ，即各轮外循环分别包含𝑛、𝑛 − 1、…、3、2 轮内循环，求和为 (𝑛−1)(𝑛+2)/2 。
- 空间复杂度 𝑂(1)、原地排序：指针 𝑖和 𝑗 使用常数大小的额外空间。
- 非稳定排序：如图 11‑3 所示，元素 nums[i] 有可能被交换至与其相等的元素的右边，导致两者相对顺序发生改变。
冒泡排序
工作原理
「冒泡排序 bubble sort」通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。如图 11‑4 所示，冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换它俩。遍历完成后，最大的元素会被移动到数组的最右端。
设数组的长度为 𝑛 ，冒泡排序的步骤如图 11‑5 所示。
- 首先，对 𝑛 个元素执行“冒泡”，将数组的最大元素交换至正确位置，
- 接下来，对剩余𝑛 − 1个元素执行“冒泡”，将第二大元素交换至正确位置。
- 以此类推，经过𝑛 − 1轮“冒泡”后，前 𝑛 − 1 大的元素都被交换至正确位置。
- 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。
代码
def bubble_sort(lst): size = len(lst) for i in range(size, 0, -1): flag = True for j in range(i-1): if lst[j] > lst[j+1]: lst[j], lst[j+1] = lst[j+1], lst[j] flag = False if flag: break return lst
算法特性
- 时间复杂度为𝑂(𝑛2)、自适应排序：各轮“冒泡”遍历的数组长度依次为𝑛 − 1、𝑛 − 2、…、2、1 ，总和为(𝑛 − 1)𝑛/2。在引入flag优化后，最佳时间复杂度可达到𝑂(𝑛)。
- 空间复杂度为𝑂(1)、原地排序：指针𝑖 和 𝑗 使用常数大小的额外空间。
- 稳定排序：由于在“冒泡”中遇到相等元素不交换。
插入排序
工作原理
「插入排序 insertion sort」是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。图 11‑6 展示了数组插入元素的操作流程。设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后再将 base 赋值给目标索引。
代码
def insert_sort(lst): size = len(lst) for i in range(size-1): for j in range(i, 0, -1): if lst[i+1] < lst[j]: lst[i+1], lst[j] = lst[j], lst[i+1] return lst def insert_sort(lst): size = len(lst) for i in range(size-1): val = lst[i+1] j = i while j>=0 and lst[j] > val: lst[j+1] = lst[j] j -= 1 lst[j+1] = val return lst
算法特性
- 时间复杂度 𝑂(𝑛2 )、自适应排序：最差情况下，每次插入操作分别需要循环𝑛 − 1、𝑛 − 2、…、2、1次，求和得到(𝑛 − 1)𝑛/2，因此时间复杂度为𝑂(𝑛2) 。在遇到有序数据时，插入操作会提前终止。当输入数组完全有序时，插入排序达到最佳时间复杂度𝑂(𝑛)。
- 空间复杂度 𝑂(1)、原地排序：指针 𝑖 和 𝑗 使用常数大小的额外空间。
- 稳定排序：在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序。
快速排序
快速排序 quick sort：是一种基于分治策略的排序算法，运行高效，应用广泛。
快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如图 11‑8 所示。
- 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
- 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
- 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。
def partition(lst, left, right): i, j = left, right while i < j: ## 必须先从右往左找 while i < j and lst[j] >= lst[left]: j -= 1 while i < j and lst[i] <= lst[left]: i += 1 lst[i], lst[j] = lst[j], lst[i] lst[left], lst[i] = lst[i], lst[left] return i def quick_sort(lst, left, right): if left >= right: return None pivot = partition(lst, left, right) quick_sort(lst, left, pivot-1) quick_sort(lst, pivot+1, right) return lst
基准数优化
快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 𝑛 − 1、右子数组长度为 0 。如此递归下去，每轮哨兵划分后的右子数组长度都为 0 ，分治策略失效，快速排序退化为“冒泡排序”。
我们可以优化哨兵划分中的基准数的选取策略我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。
优化代码
def median_three(lst, left, mid, right): # 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1 if (lst[left] < lst[mid]) ^ (lst[left] < lst[right]): return left elif (lst[mid] < lst[left]) ^ (lst[mid] < lst[right]): return mid return right def partition(lst, left, right): mid = median_three(lst, left, int(left + (right - left)/2), right) lst[mid], lst[left] = lst[left], lst[mid] i, j = left, right while i < j: ## 必须先从右往左找 while i < j and lst[j] >= lst[left]: j -= 1 while i < j and lst[i] <= lst[left]: i += 1 lst[i], lst[j] = lst[j], lst[i] lst[left], lst[i] = lst[i], lst[left] return i def quick_sort(lst, left, right): if left >= right: return None pivot = partition(lst, left, right) quick_sort(lst, left, pivot-1) quick_sort(lst, pivot+1, right) return lst
尾递归优化
在某些输入下，快速排序可能占用空间较多。以完全倒序的输入数组为例，由于每轮哨兵划分后右子数组长度为 0 ，递归树的高度会达到 𝑛 − 1 ，此时需要占用 𝑂(𝑛) 大小的栈帧空间。我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。因此这种方法能确保递归深度不超过 log 𝑛 ，从而将最差空间复杂度优化至 𝑂(log 𝑛) 。
优化代码
def median_three(lst, left, mid, right): # 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1 if (lst[left] < lst[mid]) ^ (lst[left] < lst[right]): return left elif (lst[mid] < lst[left]) ^ (lst[mid] < lst[right]): return mid return right def partition(lst, left, right): mid = median_three(lst, left, int(left + (right - left)/2), right) lst[mid], lst[left] = lst[left], lst[mid] i, j = left, right while i < j: ## 必须先从右往左找 while i < j and lst[j] >= lst[left]: j -= 1 while i < j and lst[i] <= lst[left]: i += 1 lst[i], lst[j] = lst[j], lst[i] lst[left], lst[i] = lst[i], lst[left] return i def quick_sort(nums: list[int], left: int, right: int): """ 快速排序（尾递归优化）""" while left < right: # 哨兵划分操作 pivot = partition(nums, left, right) # 对两个子数组中较短的那个执行快排 if pivot - left < right - pivot: quick_sort(nums, left, pivot - 1) # 递归排序左子数组 left = pivot + 1 # 剩余未排序区间为 [pivot + 1, right] else: quick_sort(nums, pivot + 1, right) # 递归排序右子数组 right = pivot - 1 # 剩余未排序区间为 [left, pivot - 1] return nums
算法特性
- 时间复杂度 𝑂(𝑛 log 𝑛)、自适应排序：在平均情况下，哨兵划分的递归层数为 log 𝑛 ，每层中的总循环数为 𝑛 ，总体使用 𝑂(𝑛 log 𝑛) 时间。在最差情况下，每轮哨兵划分操作都将长度为 𝑛 的数组划分为长度为 0 和 𝑛−1 的两个子数组，此时递归层数达到 𝑛 层，每层中的循环数为 𝑛 ，总体使用 𝑂(𝑛2 ) 时间。
- 空间复杂度 𝑂(𝑛)、原地排序：在输入数组完全倒序的情况下，达到最差递归深度 𝑛 ，使用 𝑂(𝑛) 栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
- 非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。
快排为什么快
- 从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。
- 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 𝑂(𝑛2 ) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 𝑂(𝑛 log 𝑛) 的时间复杂度下运行。
- 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
- 复杂度的常数系数低：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。
归并排序
归并排序(merge sort)：是一种基于分治策略的排序算法，包含图 11‑10 所示的“划分”和“合并”阶段。
- 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
- 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。
归并排序与二叉树后序遍历的递归顺序是一致的。
- 后序遍历：先递归左子树，再递归右子树，最后处理根节点。
- 归并排序：先递归左子数组，再递归右子数组，最后处理合并。
def merge(lst, left, mid, right): tmp = list(lst[left:right+1]) left_start = 0 left_end = mid - left right_start = mid - left + 1 right_end = right - left i = left_start j = right_start for k in range(left, right + 1): if i > left_end: lst[k] = tmp[j] j += 1 elif j > right_end or tmp[i] <= tmp[j]: lst[k] = tmp[i] i += 1 else: lst[k] = tmp[j] j += 1 def merge_sort(lst, left, right): if left >= right: return None mid = int(left + (right - left)/2) merge_sort(lst, left, mid) merge_sort(lst, mid+1, right) merge(lst, left, mid, right) return lst
算法特性
- 时间复杂度 𝑂(𝑛 log 𝑛)、非自适应排序：划分产生高度为 log 𝑛 的递归树，每层合并的总操作数量为𝑛 ，因此总体时间复杂度为 𝑂(𝑛 log 𝑛) 。
- 空间复杂度 𝑂(𝑛)、非原地排序：递归深度为 log 𝑛 ，使用 𝑂(log 𝑛) 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 𝑂(𝑛) 大小的额外空间。
- 稳定排序：在合并过程中，相等元素的次序保持不变。
链表排序
对于链表，归并排序相较于其他排序算法具有显著优势，可以将链表排序任务的空间复杂度优化至 𝑂(1) 。
- 划分阶段：可以通过使用“迭代”替代“递归”来实现链表划分工作，从而省去递归使用的栈帧空间。
- 合并阶段：在链表中，节点增删操作仅需改变引用（指针）即可实现，因此合并阶段（将两个短有序链表合并为一个长有序链表）无须创建额外链表。
数据结构与算法 搜索（下）https://developer.aliyun.com/article/1504031?spm=a2c6h.13148508.setting.45.36834f0eMJOehx
