解题思路

给定 N 个 IPv4 地址字符串（形如 A.B.C.D，每段为 0~255 的整数）。要求按地址的数值大小排序后，输出为“交叉顺序”：最小、最大、第二小、第二大、……。

关键做法：排序 + 双指针

1. 解析每个 IP 为 4 个整数 (A,B,C,D)，作为比较键。比较时先比 A，再比 B，再比 C，最后比 D，即按字典序升序，相当于 IP 的数值大小比较。
2. 将 (A,B,C,D, 原字符串) 排序（稳定性无要求）。
3. 用双指针 l=0, r=n-1 交替取数：依次输出 sorted[l]、sorted[r]、sorted[l+1]、sorted[r-1]……直至两指针相交。

题目内容

$IPv4$ 地址是一个由 $4$ 个 $0$ 到 $255$ 之间的整数组成的字符串，形式为 $A.B.C.D$，其中 $A、B、C$ 和 $D$ 是 $[0,255]$ 的整数。现在给定一组 $IPv4$ 地址字符串，要求按照 $IP$ 地址的数值顺序对它们进行交叉排序，即按照最小、最大、第 $2$ 小、第 $2$ 大、…、第 $N$ 小、第 $N$ 大的顺序交叉排序。

$IP$ 地址的数值比较规则

1.先比较 $A$ 的值。

2.如果 $A$ 相同，则比较 $B$ 的值。

3.如果 $A$ 和 $B$ 都相同，则比较 $C$ 的值。

4如果 $A、B$ 和 $C$ 都相同，则比较 $D$ 的值。

输入描述

1.第一行为 $IPv4$ 地址个数 $N$ ，有效范围为 $[1,100]$

2.接下来 $N$ 行，每行为一个 $IPv4$ 地址字符串

输出描述

输出排序后的 $IPv4$ 地址字符串，且用空格分隔。

样例1

输入

3
192.168.1.5
192.167.2.1
192.168.1.100

输出

192.167.2.1 192.168.1.100 192.168.1.5

说明

$IP$ 地址的格式是 $A.B.C.D$，这二个 $IP$ 地址的 $A$ 部分相同。$B$ 部分，$167$ 最小。因此 $192.167.2.1$ 排第一。

而 $192.168.1.5$ 和 $192.168.1.100$，前面的 $A、B、C$ 均相同最后的 $D$ 部分，$5$ 小于 $100$ 。因此最终的排序是

$192.167.2.1$

$192.168.1.100$

$192.168.1.5$

样例2

输入

3
100.100.100.100
9.9.9.9
11.11.11.11

输出

9.9.9.9 100.100.100.100 11.11.11.11

说明

$IP$ 地址的格式是 $A.B.C.D$ ，$9$ 的数值比 $100$ 小，$11$ 的数值比 $100$ 小。

因此按照最小、最大、第 $2$ 小的顺序排序为 $9.9.9.9$ $100.100.100.100$ $11.11.11.11$