#A. 小凯的排序课

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

为了冲击下半年的算法竞赛，小凯最近学习了八大排序算法，但是粗心大意的小凯却将八大排序算法的时空复杂度和稳定性记混了。现在，无助的小凯找到了你，希望你能给他写一个程序，输入一行字符串 s ，表示排序的英文名字。随后输出一行，时空复杂度和稳定性。

附：八大排序的时空复杂度和稳定性

排序的英文名	时间复杂度	空间复杂度	稳定性
quick sort(快速排序)	$O(nlogn)$	$O(logn)$	No
merge sort(归并排序)		$O(n)$	Yes
heap sort(堆排序)		$O(1)$	No
shell sort(希尔排序)	$O(n^{1.3 \sim 2})$	$O(1)$	No
counting sort(计数排序)	$O(n+m)$		Yes
insertion sort(插入排序)	$O(n^2)$	$O(1)$
bubble sort(冒泡排序)
selection sort(选择排序)			No

第一行一个正整数 $T(1 \leq T \leq 10^3)$ ，表示有 $T$ 组测试样例

对于每一组测试样例，每次给出一行字符串 $s$ ，表示

对于每一组测试样例，输出一行，时间复杂度，空间复杂度和稳定性，中间用空格分隔

8
quick sort
merge sort
heap sort
shell sort
counting sort
insertion sort
bubble sort
selection sort

O(nlogn) O(logn) No
O(nlogn) O(n) Yes
O(nlogn) O(1) No
O(n^{1.3~2}) O(1) No
O(n+m) O(n+m) Yes
O(n^2) O(1) Yes
O(n^2) O(1) Yes
O(n^2) O(1) No

读入一行字符串可以使用getline哦