排序算法
总结
容易考的只有：堆排序、计数排序、归并排序、快速排序
排序算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^n) | O(logn) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
需要自己选择算法时，首先从快排、归并、堆三者之间选择，因为时间复杂度都是O(nlogn)，然后再考虑空间复杂度，归并是O(n)的空间复杂度，快排是O(logn)的空间，堆是O(1)的空间，最后再从稳定性考虑，这三种算法只有归并是稳定排序。
稳定性：排序 稳定性 指的是相等元素在原输入数组中的相对位置，在排序后不变，否则排序不稳定。稳定性对于纯数字数组来说意义不大，但对于包含多个属性的类数组来说，用于比较的属性之外其他属性不同时，保持排序的稳定性就很重要了。
计数排序
计数排序是一种 非比较排序，通常 适用于整数数组，是一种利用整数特点取得 线性复杂度 的非比较排序方法。假设待排序数组 arr 为正整数数组， 朴素 的计数排序过程如下：
- 创建一个计数数组countArr，其大小为arr中的最大值max再加1。
- 遍历arr，每读取一个arr[i]，直接令countArr[arr[i]]+=1。
- 从下标1开始遍历countArr，依次输出counter[i]个i，即为排序结果。
朴素做法有两个明显的缺陷，首先是 无法处理负数，其次是当元素个数较多，但很多相等元素使得元素分布 集中在较小范围 时，max+1 大小的 countArr 中大部分空间是多余的。改进方法很简单，即创建大小为 max - min + 1 的 countArr， max 和 min 分别是 arr 中最大和最小元素。后续代码均会采用该改进。
def count_sort(arr): min_ = min(arr) max_ = max(arr) count_arr = [0] * (max_ - min_ + 1) for n in arr: count_arr[n-min_] += 1 res = [] for i in range(len(count_arr)): res += [i+min_] * count_arr[i] return res
时间复杂度：朴素版为 O(max)，max为原数组中最大值。改进版为 O(n + k)，n为元素个数，k 计数数组大小。当元素个数较少但最大最小值差值很大时，复杂度取决于 k。
空间复杂度：countArr的大小为k+1，故空间复杂度为 O(k)
稳定性：不稳定
快速排序
基本形式
对序列
L 进行排序时：- 若
L为空，则排序结果明显为空。这是边界情况；
- 否则，在
L中任选一个元素作为pivot，然后递归地将L中不大于pivot的元素排序，将结果置于pivot的左侧；同时递归地将所有大于pivot的元素排序，将结果置于pivot的右侧。
def quick_sort(arr): if len(arr) <= 1: # 基线条件 return arr else: # 递归条件 pivot = arr[0] less_arr = [i for i in arr[1:] if i <= pivot ] great_arr = [i for i in arr[1:] if i > pivot ] return quick_sort(less_arr) + [pivot ] + quick_sort(great_arr)
划分（partition）
观察前面的基本快速排序算法，会发现每一层遍历了两次：
- 第一次遍历获得了所有不大于
pivot的元素
- 第二次遍历获得了所有大于
pivot的元素
其实可以将他们合并成只遍历一次的划分过程。
下图描述了这种一次遍历进行划分的方法。从左向右逐一处理数组中的元素。任何时候，数组都由下图（a）所示的几部分组成：
- 最左侧为
pivot，当划分过程结束时，pivot会被移动到最终的位置
- 一段只包含不大于
pivot的元素的部分。这一段的右侧边界被标记为L
- 一段只包含大于
pivot的元素的部分。这一段的右侧边界被标记为R
R标记后面的元素尚未被处理。这部分的元素可能大于，也可能不大于pivot
在划分过程开始的时候，
L 标记指向pivot，R 标记指向pivot 后的下一个元素，如图 (b) 所示。然后算法不断地向右侧移动R 标记进行处理，直到R 标记越过数组的右侧边界。每次迭代，都比较
R 标记指向的元素和pivot 的大小。若大于pivot，这一元素应该位于L 和R 标记之间，算法继续向前移动R 标记以检查下一个元素；否则，说明R 标记指向的元素小于或者等于pivot（不大于），它应该位于L 标记的左侧。为此，我们将L 标记向前移动一步，然后交换L 和R 标记指向的元素。当
R 标记越过最后一个元素时，所有的元素都已处理完毕。大于pivot 的元素都被移动到了L 标记的右侧，而其他元素位于L 标记的左侧。此时我们需要移动pivot元素，使得它位于这两段的中间。为此，我们可以交换pivot 和L 标记指向的元素。如图 (c) 中的双向箭头所示。L 标记最终指向pivot，它将整个的数组分成了两部分。我们将L 标记作为划分过程的结果返回。def quickSort(nums, start, end): ''' [start, end] ''' if start >= end: return idx = partition(nums, start, end) quickSort(nums, start, idx-1) quickSort(nums, idx+1, end) return nums def partition(nums, start, end): # 随机选择一个下标作为主轴，然后和第一个交换，形式上就相当于是第一个为主轴 pivot = random.randint(start, end) pivot, start = start, povit pivot = nums[start] L = start # 小于等于主元的序列 最右边的下标 for R in range(L+1, end+1): # 当前值位置没错 if nums[R] > pivot: continue # 当前值应该位于L左侧的 # 所以先将L右移动，然后和当前值交换 elif nums[R] <= pivot: L += 1 nums[L], nums[R] = nums[R], nums[L] nums[L], nums[start] = nums[start],nums[L] return L
时间复杂度：参考快速排序时间复杂度分析 - 知乎 (zhihu.com)。平均和最好情况下，每一次划分都正好将数组分成长度相等的两半 。最坏情况下，当输入为已排序数组，且每一次划分都将数组分成了0和n-1两部分
空间复杂度：递归形式的快排，取决于递归深度，为 O(logn)
稳定性：不稳定。partition中在确定了主轴位置后，将一开始设置的主轴元素与最后一个小于主轴的元素x交换时，若中间有与x同值的元素，则稳定性被破坏。例：7 2 4 4 8 9，7为主轴元素，partition过后交换7和第二个4，则两个4的位置关系发生变化。
归并排序（自顶向下递归）
归并排序利用的是递归的思路，将数组（or链表）分成两半，再分别将两个子数组（or子链表）排序之后再将他们合并成一个排序的数组（or链表）。其实是没有一个显式排序的过程的，主要体现在合并的过程上，因为都是分成最多两个元素（or节点）然后比大小合并的，合并的时候比大小。
def merge_sort(arr): if len(arr) <= 1: return arr l = self.merge_sort(arr[:len(arr)//2]) r = self.merge_sort(arr[len(arr)//2:]) return merge(l, r) def merge(l, r): res = [] p1, p2 = 0, 0 while p1 < len(l) and p2 < len(r): if l[p1] <= r[p2]: res.append(l[p1]) p1 += 1 else: res.append(r[p2]) p2 += 1 if p1 < len(l): res.extend(l[p1:]) else: res.extend(r[p2:]) return res
时间复杂度：在每一层递归中(这里的一层指的是 递归树 中的层)，比较和赋值的时间复杂度都是 O(n)，数组规模减半次数为 logn，即递归深度为 logn，也即总共需要 logn 次 O(n) 的比较和赋值，时间复杂度为 O(nlogn)。
空间复杂度：递归深度为 logn，递归过程中需要一个长度为 n 的临时数组保存中间结果，空间复杂度为 O(n)
稳定性：稳定，合并时的此判断中的等号
if(left[p1] <= right[p2])，保证了出现相等元素时，居左的元素总会被放在左侧，稳定性不受影响。冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。这样每一轮比较之后，最大的数都会放在最右端。
改进版冒泡排序：
- 冒泡界优化：冒泡排序第1次遍历后会将最大值放到最右边，这个最大值也是全局最大值。因此可以记录前一轮交换的最终位置，说明该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。
- 提前结束优化：当某一轮比较均未发生交换，说明排序已完成，可设置一个布尔值记录一轮排序是否有发生交换，若无则提前退出循环结束程序。
def bubbleSort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-1): if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr # ----------------- def bubbleSort(arr): for i in range(1, len(arr)): is_sweped = False for j in range(0, len(arr)-i): if arr[j] > arr[j+1]: is_sweped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] # 本轮没有交换，说明已经是有序状态了 if is_sweped is False: break return arr
时间复杂度：两层
for 循环，第 1 轮比较 n−1 次 (n = arr.length) ，最后一轮比较 1 次。总比较次数为 n*(n - 1) / 2 次，时间复杂度为 O(n^2)。当输入数组为已排序状态时，在应用提前结束优化的情况下，只需一轮比较，此时为最佳时间复杂度 。空间复杂度：算法中只有常数项变量，。
稳定性：为稳定排序，因为相同的元素不会被交换，因此位置不会改变
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
def select_sort(arr): for i in range(0, len(arr)): # 找最小元素的下标 min_idx = i for j in range(i+1, len(arr)): if arr[i] < arr[min_idx]: min_idx = i # swap arr[min_idx], arr[i] = arr[i], arr[min_idx] return arr
时间复杂度：两层
for循环，第1轮比较 n - 1 次(n = arr.length)，最后一轮比较1次。总比较次数为 n*(n - 1) / 2次，时间复杂度为 O(n^2)。冒泡排序和选择排序的比较次数均为 O(n^2)，但选择排序的交换次数是 O(n)，而冒泡排序的平均交换次数仍然是二次的。空间复杂度：算法中只有常数项变量，O(1)O。
稳定性：不稳定排序。存在跨越交换。找到本轮次最小值之后，将其与本轮起始数字交换，此时若中间有与起始元素同值的元素，将打破稳定性。例: 7 7 2 。第一轮交换第一个7和2，则两个7位置关系改变。
插入排序
对于待排序数组，从第2个元素开始(称作插入对象元素)，比较它与之前的元素(称作比较对象元素)，当插入对象元素小于比较对象元素时，继续往前比较，直到不小于(≥)比较对象，此时将插入对象元素插入到该次比较对象元素之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作。
时间复杂度：两层for循环，外层总轮次为n - 1轮(n = arr.length)，当原数组逆序时，移动次数为 n*(n - 1) / 2次，最坏时间复杂度为 O(n^2)，平均时间复杂度同为 O(n^2)。当原数组已基本有序时，接近线性复杂度 O(n)。例如原数组已完全排序，则算法只需比较 n - 1 次。
※ 折半插入总的查找(比较)次数虽为 O(nlogn)，但平均移动 (每轮移动一半的数字) 次数仍是 O(n^2)
空间复杂度：算法中只有常数项变量，O(1)O(1)。
稳定性：简单插入和折半插入(二分插入)排序是稳定的。对于大小相同的两个数字，简单插入和折半插入均使得后来的数字靠右放置 （因为条件是 ≥），因此不会改变其相对位置。
速通
排序算法完整笔记参见 排序算法
常考的包括：快速排序，归并排序，堆排序，桶排序（计数排序）等。
