排序简介 · NSOI Guide

排序方法使用库函数排序静态数组动态数组由数对和元组组成的（动态）数组题目检查你的理解

排序是指按某种特定顺序排列各个元素。

排序方法

Focus Problem – try your best to solve this problem before continuing!

Resources
		CPH	3.1 - 排序理论	冒泡排序、归并排序、计数排序
		CSA	排序	选择排序、插入排序、冒泡排序、归并排序

使用库函数排序

虽然通常不需要了解排序的具体实现，但你应该知道如何使用内置方法。

Resources
		PY	排序指南	参考资料

静态数组

Python 使用 array 模块创建静态数组。Python 没有为数组提供内置排序方法，但可以使用 sorted() 函数把数组当作列表排序并返回一个列表，再将列表转换回数组。

from array import array

# "i" denotes integer type of array elements
arr = array("i", [5, 1, 3, 2, 4])

print(arr)  # Outputs the original array
print(sorted(arr))  # Outputs the sorted array, converted to a list

arr = array("i", sorted(arr))  # Sorting, then converting back into an array
print(arr)

动态数组

Python 中主要有两种列表排序方法。sorted(arr) 返回新列表而不修改原列表； arr.sort() 则会原地排序列表。

arr = [5, 1, 3, 2, 4]
print(sorted(arr))  # Outputs [1, 2, 3, 4, 5]
print(arr)  # Outputs the original array

arr.sort()
print(arr)  # Outputs [1, 2, 3, 4, 5]

关于 Python 排序的更多信息，请参阅此链接。

由数对和元组组成的（动态）数组

默认情况下，Python 元组先按第一个元素排序；若相同则比较第二个元素，并依次类推。

arr = [(1, 5), (2, 3), (1, 2)]
arr = sorted(arr)
print(arr)  # Outputs [(1, 2), (1, 5), (2, 3)]

题目

Warning!

铜组题目的设计保证你不需要 $\mathcal{O}(N\log N)$ 的排序（以 $\mathcal{O}(N^2)$ 的时间反复取出最小值总是足够的）。

Source	Problem Name	Difficulty	Tags
CSES	Distinct Numbers	Easy	Show Tags Sorting
CF	Playing in a Casino	Easy	Show Tags Sorting
CF	Kayaking	Medium	Show Tags Greedy, Sorting
Bronze	Why Did the Cow Cross the Road III	Medium	Show Tags Simulation, Sorting
Bronze	Cow College	Medium	Show Tags Sorting
Bronze	Angry Cows	Hard	Show Tags Simulation, Sorting
CF	Permutator	Hard	Show Tags Greedy, Sorting

注意：集合简介模块中还有更多排序题。

检查你的理解

数组 $[7,2,6,3,1]$ 经过一轮冒泡排序后会变成什么？

Question 1 of 4

Table of Contents