排序
程序设计中，排序算法通常有三类：比较排序、非比较排序和混合排序。
- 比较排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 $O(n\log n)$，因此也称为非线性时间比较类排序。
- 非比较排序：不通过比较来决定元素间的相对次序，它可以突破比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
- 混合排序：通过比较和非比较两种方法来进行排序，其时间复杂度介于上述两种之间，因此也称为线性对数比较类排序。
比较排序：通过比较元素之间的大小关系，逐一比较和交换元素的位置，使得排序后的元素满足总体有序的性质。常见的比较排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等。其中，快速排序、归并排序、堆排序都具有O(nlogn)的时间复杂度（最坏情况下）。
非比较排序：通过某种特殊的技术（如桶排序、计数排序、基数排序）来实现排序，不基于比较元素之间大小的关系。在一定的条件下，非比较排序算法的时间复杂度可以达到O(n)的线性复杂度。例如，计数排序和基数排序适用于排序值在一定范围内的整数序列，时间复杂度均为O(n+k)，其中k为正整数。
混合排序：结合两种或多种不同的排序算法，根据不同的数据属性和大小来选择更适合的排序算法。例如，C++标准库的sort函数就是一种经典的混合排序算法，它包括快速排序、插入排序、堆排序三种排序算法，会根据数据的大小和类型自适应地选择排序算法。
排序算法的选择取决于任务的特征和时间/空间的限制，不同的排序.
离散化
离散化可以映射无穷大集合中的若干个元素到有限集合以便于统计。
例如，问题的范围虽然定义在整数集合，但只涉及其中m个有限值，并且与数值的绝对大小无关。此时可以将整数集合中的m个整数与1~m建立映射关系。如果有一个时间、空间复杂度与数值范围大小有关的算法，在离散化后的复杂度均将降低为与m有关。
具体的说，假设问题涉及的数值范围为int的n个整数，$n$为数值个数，$m$为离散化后的数值个数，$a_i$为原始数值，$b_i$为离散化后的数值。
可以将a数组排序去重后，得到有序数组b，在数组b的下标i与数值b[i]之间建立映射关系。若要查询整数i代替的数值，只需要返回 b[i]，若要查询整数a[j]被哪一个1~m的整数代替，只需要返在b中二分查找a[j]的位置。
例题 AcWing 103 电影
Description
莫斯科正在举办一个大型国际会议，有 n 个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见，我们把世界上的所有语言用 1 到 $10^9$ 之间的整数编号。
在会议结束后，所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有 m 部电影正在上映，每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影，可以让观影很开心的人最多。
如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。
Input
第一行输入一个整数 n，代表科学家的数量。
第二行输入 n 个整数 a1,a2…an，其中 ai 表示第 i 个科学家懂得的语言的编号。
第三行输入一个整数 m，代表电影的数量。
第四行输入 m 个整数 b1,b2…bm，其中 bi 表示第 i 部电影的语音采用的语言的编号。
第五行输入 m 个整数 c1,c2…cm，其中 ci 表示第 i 部电影的字幕采用的语言的编号。
请注意对于同一部电影来说，bi≠ci。
同一行内数字用空格隔开。
Output
输出一个整数，代表最终选择的电影的编号。电影编号 1∼m。
如果答案不唯一，输出任意一个均可。
Range
$1≤n,m≤200000,1≤ai,bi,ci≤10^9$
Sample Input
3
2 3 2
2
3 2
2 3
Sample Output
2
中位数
中位数是指将一组数据按照从小到大的顺序排列，位于中间位置的数。如果数据的个数是奇数，则中位数是最中间的那个数；如果数据的个数是偶数，则中位数是中间两个数的平均数。当结果与绝对位置无关，但与相对位置有关时，可以使用中位数来代替绝对位置。
例题 AcWing 104 货舱选址
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
Input
第一行输入整数 N。
第二行 N 个整数 A1∼AN。
Output
输出一个整数，表示距离之和的最小值。
Range
$1≤N≤100000,0≤Ai≤40000$
Sample Input
4
6 2 9 1
Sample Output
12
N = int(input())
ans = 0
nums = list(map(int, input().split()))
nums.sort()
idx = len(nums) // 2 if len(nums) % 2 != 0 else (len(nums) + 1) // 2
for num in nums:
ans += abs(num - nums[idx])
print(ans)
第K大数
利用快速排序将数组分为左右半段，设置一个基准，大于基准的值设置为cnt，如果k<=cnt，在左半段寻找第第k大数，如果k> cnt，则在右半段寻找第k-cnt大数。并且不断递归。复杂度可以从快速排序的 $O(n\log n)$ 趋近于 $O(n)$ 。
逆序对
对于一个序列a，若i< j且a[i]>a[j]，则称a[i]、a[j]构成逆序对。
使用归并排序可以在$O(n\log n)$内求出一个长度为n的序列中逆序对的个数。归并排序每次将序列二分，递归对左右两半排序，然后合并序列。
具体的思路是，在归并排序的过程中，在合并两个有序子序列时，需要统计此时的逆序对数。假设已经将a[left, mid]和a[mid+1, right]两个有序子序列合并成a[left, right]，那么当前的逆序对数就是左半边有逆序对加右半边有逆序对再加上左右两个子序列之间的逆序对数。这可以通过“分治+归并”地思想来解决。
例题 AcWing 107 超快速排序
在这个问题中，您必须分析特定的排序算法----超快速排序。
该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序。
对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
Input
输入包括一些测试用例。
每个测试用例的第一行输入整数 n，代表该用例中输入序列的长度。
接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据，第 i 行的数据代表序列中第 i 个数。
当输入用例中包含的输入序列长度为 0 时，输入终止，该序列无需处理。
Output
对于每个需要处理的输入序列，输出一个整数 op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。
Range
$0≤n<500000$,一个测试点中，所有 n 的和不超过 500000。
$0≤ai≤999999999$
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
"""
题目要求实际上是冒泡排序。结果为冒泡排序最少操作次数，即逆序对个数。
"""
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left_arr, left_cnt = merge_sort(arr[:mid])
right_arr, right_cnt = merge_sort(arr[mid:])
combined_arr, cross_cnt = merge(left_arr, right_arr)
return combined_arr, left_cnt + right_cnt + cross_cnt
def merge(left_arr, right_arr):
i = j = 0
cnt = 0
merged = []
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] > right_arr[j]:
merged.append(right_arr[j])
j += 1
cnt += len(left_arr) - i
else:
merged.append(left_arr[i])
i += 1
merged += left_arr[i:]
merged += right_arr[j:]
return merged, cnt
arr = []
while x := int(input()):
arr.append(x)
print(merge_sort(arr))
排序算法总览
选择排序
选择排序是一种简单直观的排序算法。它的工作原理是每次找出第 i 小的元素（也就是 ￥A_{i..n}￥ 中最小的元素），然后将这个元素与数组第 i 个位置上的元素交换。
def selection_sort(a, n):
for i in range(1, n):
ith = i
for j in range(i + 1, n + 1):
if a[j] < a[ith]:
ith = j
a[i], a[ith] = a[ith], a[i]
冒泡排序
冒泡排序是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。
def bubble_sort(a, n):
flag = True
while flag:
flag = False
for i in range(1, n):
if a[i] > a[i + 1]:
flag = True
a[i], a[i + 1] = a[i + 1], a[i]
插入排序
插入排序是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。
def insertion_sort(arr, n):
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
计数排序
计数排序是一种线性时间的排序算法。
计数排序的工作原理是使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数，然后根据数组 C 来将 A 中的元素排到正确的位置。
它的工作过程分为三个步骤：
- 计算每个数出现了几次；求出每个数出现次数的 前缀和；
- 利用出现次数的前缀和，
- 从右至左计算每个数的排名。
计算前缀和是因为直接将 C 中正数对应的元素依次放入 A 中不能解决元素重复的情形。
我们通过为额外数组 C 中的每一项计算前缀和，结合每一项的数值，就可以为重复元素确定一个唯一排名：
额外数组 C 中每一项的数值即是该 key 值下重复元素的个数，而该项的前缀和即是排在最后一个的重复元素的排名。
如果按照 A 的逆序进行排列，那么显然排序后的数组将保持 A 的原序（相同 key 值情况下），也即得到一种稳定的排序算法。
N = W = 100010
n = w = 0
a = b = [0] * N
cnt = [0] * W
def counting_sort():
for i in range(1, n + 1):
cnt[a[i]] += 1
for i in range(1, w + 1):
cnt[i] += cnt[i - 1]
for i in range(n, 0, -1):
b[cnt[a[i]] - 1] = a[i]
cnt[a[i]] -= 1
快速排序
快速排序，又称分区交换排序，简称「快排」，是一种被广泛运用的排序算法。
快速排序的工作原理是通过 分治 的方式来将一个数组排序。
快速排序分为三个过程：
- 将数列划分为两部分（要求保证相对大小关系）；
- 递归到两个子序列中分别进行快速排序；
- 不用合并，因为此时数列已经完全有序。
和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。
之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。
其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都有不止一种实现方法。
第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。
当接近$O(n^2)$情况时，可以考虑朴素优化、三路快速排序、内省排序等来优化。
def quick_sort(alist, first, last):
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
quick_sort(alist, first, low - 1)
quick_sort(alist, low + 1, last)
归并排序
归并排序是高效的基于比较的稳定排序算法。
归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 $\Theta (n \log n)$，空间复杂度为 $\Theta (n)$。
归并排序可以只使用 $\Theta (1)$ 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。
归并排序分为合并和分治两部分。
最核心的部分是合并（merge）过程：将两个有序的数组 left_arr[i] 和 right_arr[j] 合并为一个有序数组 combined_arr[k]。
从左往右枚举 left_arr[i] 和 right_arr[j]，找出最小的值并放入数组 combined_arr[k]；重复上述过程直到 left_arr[i] 和 right_arr[j] 有一个为空时，将另一个数组剩下的元素放入 combined_arr[k]。
为保证排序的稳定性，前段首元素小于或等于后段首元素时（left_arr[i] <= right_arr[j]）而非小于时（left_arr[i] < right_arr[j]）就要作为最小值放入 combined_arr[k]。
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0 # 递归边界，一个元素已经是有序的，同时逆序对个数为0。
mid = len(arr) // 2
left_arr, left_cnt = merge_sort(arr[:mid]) # 递归划分左部分
right_arr, right_cnt = merge_sort(arr[mid:]) # 递归划分右部分
combined, cross_cnt = merge(left_arr, right_arr) # 归并左右两部分并计数逆序对
return combined, left_cnt + right_cnt + cross_cnt # 返回排序后的数组和逆序对总数
def merge(left_arr, right_arr):
""" 归并，并计算逆序对 """
i = j = 0
count = 0
merged = []
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] > right_arr[j]:
merged.append(right_arr[j])
j += 1
count += len(left_arr) - i
else:
merged.append(left_arr[i])
i += 1
merged += left_arr[i:]
merged += right_arr[j:]
return merged, count
基数排序*
基数排序是一种非比较型的排序算法，最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为 k 个关键字，逐一对各个关键字排序后完成对所有元素的排序。
如果是从第 1 关键字到第 k 关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；
如果是从第 k 关键字到第 1 关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序。
堆排序*
堆排序是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。
堆排序的本质是建立在堆上的选择排序。
桶排序*
桶排序是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。
桶排序按下列步骤进行：
- 设置一个定量的数组当作空桶；
- 遍历序列，并将元素一个个放到对应的桶中；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把元素再放回原来的序列中。
希尔排序*
希尔排序，也称为缩小增量排序法，是 插入排序 的一种改进版本。希尔排序以它的发明者希尔）命名。
排序对不相邻的记录进行比较和移动：
- 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
- 对这些子序列进行插入排序；
- 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。