{ }codelper
列表排序P0320

数值顺序和字典顺序

把 n 个整数按两种顺序排列。
第一种是数值顺序,从小的数开始依次排列。
第二种是字典顺序,把数看作输入中写出的原样字符串来比较。
两个字符串从前往后逐个字符比较,第一个不同的字符更靠前的一方排在前面,字符的先后是 -、0、1、…、9。
如果一个字符串与另一个字符串的开头部分完全相同,短的排在前面。
第一行给出 n,第二行给出 n 个整数,用一个空格隔开。
第一行按数值顺序、第二行按字典顺序输出这 n 个数,用一个空格隔开。
相同的数出现几次就输出几次。
第三行输出两行中同一位置上放着相同的数的位置个数。

输入
1 ≤ n ≤ 1,000。
整数在 -2,000,000,000 到 2,000,000,000 之间,只用数字给出,不带逗号。
负数以 - 开头,不会带 + 号或多余的 0(007、-0)
输出
三行:数值顺序、字典顺序、同一位置上放着相同的数的位置个数
样例 1 · stdin
6
10 9 -3 100 -20 9
stdout
-20 -3 9 9 10 100
-20 -3 10 100 9 9
2
样例 2 · stdin
2
2000000000 -2000000000
stdout
-2000000000 2000000000
-2000000000 2000000000
2
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写?查看各语言题解 · 8 种语言题解

同一个排序工具,会根据里面装的是什么来决定不同的顺序。
Python sorted(tokens, key=int) 按转成数后的值比较,sorted(tokens) 按字符串原样比较。
Java Arrays.sort 对 int[] 是数值顺序,对 String[] 是字典顺序;C++ std::sort 对 vector<int> 和 vector<string> 也是这样不同。
Craykon 列表.排序() 同样是数的列表按数值、字符串的列表按字典顺序。
C qsort 必须传入比较函数,数用 (x > y) - (x < y),字符串用 strcmp。
C# 用 Array.Sort(byNum) 和 Array.Sort(byText, StringComparer.Ordinal),告诉它字符串按字符编码比较(默认比较遵循区域文化规则;本题只有 - 和数字,在评测环境中两者结果相同,但明确指定按字符编码比较更稳妥)。
只有 JS·TS 是反过来的:什么都不传的 sort() 是字典顺序,数值顺序必须传入比较函数 sort((x, y) => x - y)。
四个陷阱:① 不转成数,或者不告诉它怎么比较,第一行就会变成字典顺序(示例 1 的第一行变成 -20 -3 10 100 9 9)。
JS nums.sort() 即使是数的数组也会转成字符串比较;Python 漏掉 key=int,或在 Craykon 中不用 转数字 就对字符串列表 排序(),也是如此。
② 原地排序不会创建副本。
JS sort 对那个数组排序后原样返回它,所以 const byNum = nums.sort(...) 和 const byText = nums.sort() 是同一个数组。
Python by_num = tokens 也不是复制。
两行会变得一样,第三行变成 n(示例 1 变成 6)。
用 JS [...tokens]、Python sorted、Java clone()、Craykon 子列表(0, n) 分别创建。
③ Python by_num = tokens.sort(key=int) 存下的不是排好的列表而是 None,在用到它的那一行会因 TypeError 停止。
④ 把比较函数写成减法的 C return x - y; 和 Java (x, y) -> x - y,在 2000000000 - (-2000000000) 时超出 int 范围变成负数,于是大的数被排在前面(示例 2 的第一行变成 2000000000 -2000000000)。
C 用 (x > y) - (x < y),Java 用 Integer.compare(x, y)。
JS 的 x - y 因为数是浮点数,在这个范围内不会溢出。

Pythonmain.py · 12 行
n = int(input())tokens = input().split() # sorted는 새 목록을 돌려주고 원래 목록은 그대로 둔다by_num = sorted(tokens, key=int)  # 수로 바꾼 값을 기준으로: 수 크기 순서by_text = sorted(tokens)          # 문자열 그대로: 사전 순서 same = sum(1 for x, y in zip(by_num, by_text) if x == y) print(*by_num)print(*by_text)print(same)
JavaScriptmain.js · 18 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const tokens = lines[1].trim().split(/\s+/); // sort는 그 배열 자체를 정렬하므로, 순서마다 배열을 따로 만든다// 수 크기 순서는 견주는 함수를 꼭 넘겨야 한다const byNum = tokens.map(Number).sort((x, y) => x - y);// 아무것도 넘기지 않은 sort()는 문자열로 견준다: 사전 순서const byText = [...tokens].sort(); let same = 0;for (let i = 0; i < n; i++) {  if (byNum[i] === Number(byText[i])) same++;} console.log(byNum.join(" "));console.log(byText.join(" "));console.log(same);
TypeScriptmain.ts · 19 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const tokens: string[] = lines[1].trim().split(/\s+/); // sort는 그 배열 자체를 정렬하므로, 순서마다 배열을 따로 만든다// 수 크기 순서는 견주는 함수를 꼭 넘겨야 한다const byNum: number[] = tokens.map(Number).sort((x: number, y: number) => x - y);// 아무것도 넘기지 않은 sort()는 문자열로 견준다: 사전 순서const byText: string[] = [...tokens].sort(); let same: number = 0;for (let i = 0; i < n; i++) {  if (byNum[i] === Number(byText[i])) same++;} console.log(byNum.join(" "));console.log(byText.join(" "));console.log(same);
JavaMain.java · 37 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(in.readLine().trim());        String[] tokens = in.readLine().trim().split(" +");         // int 배열을 정렬하면 수 크기 순서        int[] byNum = new int[n];        for (int i = 0; i < n; i++) byNum[i] = Integer.parseInt(tokens[i]);        Arrays.sort(byNum);         // String 배열을 정렬하면 사전 순서. clone으로 복사본을 만들어 정렬한다        String[] byText = tokens.clone();        Arrays.sort(byText);         int same = 0;        StringBuilder numLine = new StringBuilder();        StringBuilder textLine = new StringBuilder();        for (int i = 0; i < n; i++) {            if (byNum[i] == Integer.parseInt(byText[i])) same++;            if (i > 0) {                numLine.append(' ');                textLine.append(' ');            }            numLine.append(byNum[i]);            textLine.append(byText[i]);        }        System.out.println(numLine);        System.out.println(textLine);        System.out.println(same);    }}
C#Main.cs · 28 行
using System; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        string[] tokens = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);         // int 배열을 정렬하면 수 크기 순서        int[] byNum = Array.ConvertAll(tokens, int.Parse);        Array.Sort(byNum);         // 문자열은 StringComparer.Ordinal을 넘겨 글자 코드 순서(사전 순서)로 정렬한다        string[] byText = (string[])tokens.Clone();        Array.Sort(byText, StringComparer.Ordinal);         int same = 0;        for (int i = 0; i < n; i++)        {            if (byNum[i] == int.Parse(byText[i])) same++;        }         Console.WriteLine(string.Join(" ", byNum));        Console.WriteLine(string.Join(" ", byText));        Console.WriteLine(same);    }}
C++main.cpp · 28 行
#include <algorithm>#include <iostream>#include <string>#include <vector> int main() {    int n;    std::cin >> n;    std::vector<std::string> byText(n);    std::vector<int> byNum(n);    for (int i = 0; i < n; i++) {        std::cin >> byText[i];        byNum[i] = std::stoi(byText[i]);    }     // 같은 std::sort지만 int는 수 크기로, std::string은 사전 순서로 견준다    std::sort(byNum.begin(), byNum.end());    std::sort(byText.begin(), byText.end());     int same = 0;    for (int i = 0; i < n; i++) {        if (byNum[i] == std::stoi(byText[i])) same++;    }     for (int i = 0; i < n; i++) std::cout << byNum[i] << (i + 1 < n ? ' ' : '\n');    for (int i = 0; i < n; i++) std::cout << byText[i] << (i + 1 < n ? ' ' : '\n');    std::cout << same << '\n';}
Cmain.c · 39 行
#include <stdio.h>#include <stdlib.h>#include <string.h> /* 수 크기로 견준다. 빼기(x - y)는 int 범위를 넘칠 수 있어서 쓰지 않는다 */static int by_num(const void *a, const void *b) {    int x = *(const int *)a, y = *(const int *)b;    return (x > y) - (x < y);} /* 문자열로 견준다. strcmp가 바로 사전 순서다 */static int by_text(const void *a, const void *b) {    return strcmp((const char *)a, (const char *)b);} int main(void) {    int n;    static int nums[1000];    static char texts[1000][12]; /* "-2000000000"은 11글자, 끝 표시까지 12칸 */    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%11s", texts[i]);        nums[i] = atoi(texts[i]);    }     /* qsort는 견주는 함수를 받는다. 배열마다 다른 함수를 넘긴다 */    qsort(nums, n, sizeof nums[0], by_num);    qsort(texts, n, sizeof texts[0], by_text);     int same = 0;    for (int i = 0; i < n; i++) {        if (nums[i] == atoi(texts[i])) same++;    }     for (int i = 0; i < n; i++) printf("%d%c", nums[i], i + 1 < n ? ' ' : '\n');    for (int i = 0; i < n; i++) printf("%s%c", texts[i], i + 1 < n ? ' ' : '\n');    printf("%d\n", same);    return 0;}
Craykonmain.cray · 27 行
n = 控制台.读行().转数字();tokens = 控制台.读行().去空白().分割(); // 정렬()은 그 목록 자체를 정렬한다. 수 목록은 수 크기 순서가 된다byNum = [];遍历 (t 在 tokens){    byNum.添加(t.转数字());}byNum.排序(); // 문자열 목록은 사전 순서가 된다. 부분목록으로 복사본을 만들어 정렬한다byText = tokens.子列表(0, n);byText.排序(); same = 0;循环 (i = 0; i < n; i++){    如果 (byNum[i] == byText[i].转数字())    {        same++;    }} 控制台.输出(byNum.连接(" "));控制台.输出(byText.连接(" "));控制台.输出(same);