解题思路

给定 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]……直至两指针相交。

   • 若 l==r，说明剩一个中位元素，直接输出即可。

复杂度分析

• 解析：O(N)
• 排序：O(N log N)
• 交叉输出：O(N)
• 总时间复杂度：O(N log N)；空间复杂度：O(N)（保存解析结果）。在 N ≤ 100 的范围内，非常充裕。

代码实现

Python

import sys

def cross_sort_ips(ips):
    items = []
    for s in ips:
        # 按 '.' 切分为四段整数，作为比较键
        a, b, c, d = map(int, s.split('.'))
        items.append(((a, b, c, d), s))

    # 按四段数值升序排序
    items.sort(key=lambda x: x[0])

    # 双指针交叉取出原字符串
    res = []
    l, r = 0, len(items) - 1
    while l <= r:
        res.append(items[l][1])   # 取当前最小
        if l == r:                # 只剩一个时结束
            break
        res.append(items[r][1])   # 取当前最大
        l += 1
        r -= 1
    return res

def main():
    data = sys.stdin.read().strip().splitlines()
    n = int(data[0].strip())
    ips = [data[i + 1].strip() for i in range(n)]
    ans = cross_sort_ips(ips)
    print(" ".join(ans))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {

    static List<String> crossSortIPs(List<String> ips) {
        // 解析为四段整数并保存原串
        class Node {
            int a, b, c, d; String s;
            Node(int a, int b, int c, int d, String s){ this.a=a; this.b=b; this.c=c; this.d=d; this.s=s; }
        }

        List<Node> list = new ArrayList<>();
        for (String s : ips) {
            // 将 '.' 替换为空格再用 Scanner/拆分读取
            String t = s.replace('.', ' ');
            String[] parts = t.trim().split("\\s+");
            int a = Integer.parseInt(parts[0]);
            int b = Integer.parseInt(parts[1]);
            int c = Integer.parseInt(parts[2]);
            int d = Integer.parseInt(parts[3]);
            list.add(new Node(a, b, c, d, s));
        }

        // 按 A,B,C,D 升序
        list.sort((x, y) -> {
            if (x.a != y.a) return x.a - y.a;
            if (x.b != y.b) return x.b - y.b;
            if (x.c != y.c) return x.c - y.c;
            return x.d - y.d;
        });

        // 双指针交叉取
        List<String> res = new ArrayList<>();
        int l = 0, r = list.size() - 1;
        while (l <= r) {
            res.add(list.get(l).s);       // 取当前最小
            if (l == r) break;            // 剩一个元素
            res.add(list.get(r).s);       // 取当前最大
            l++; r--;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine().trim());
        List<String> ips = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ips.add(sc.nextLine().trim());
        }
        List<String> ans = crossSortIPs(ips);
        // 空格分隔输出
        System.out.println(String.join(" ", ans));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

vector<string> cross_sort_ips(const vector<string>& ips) {
    struct Node {
        int a, b, c, d;
        string s;
        bool operator<(const Node& other) const {
            if (a != other.a) return a < other.a;
            if (b != other.b) return b < other.b;
            if (c != other.c) return c < other.c;
            return d < other.d;
        }
    };

    vector<Node> v; v.reserve(ips.size());
    for (auto &s : ips) {
        // 将 '.' 替换为空格，再用字符串流读取四段整数
        string t = s;
        for (char &ch : t) if (ch == '.') ch = ' ';
        stringstream ss(t);
        int a, b, c, d;
        ss >> a >> b >> c >> d;
        v.push_back({a, b, c, d, s});
    }

    sort(v.begin(), v.end()); // 按 A,B,C,D 升序

    // 双指针交叉取出原字符串
    vector<string> res;
    int l = 0, r = (int)v.size() - 1;
    while (l <= r) {
        res.push_back(v[l].s);     // 最小
        if (l == r) break;
        res.push_back(v[r].s);     // 最大
        ++l; --r;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    string line;
    vector<string> ips;
    ips.reserve(n);
    for (int i = 0; i < n; ++i) {
        cin >> line;
        ips.push_back(line);
    }

    vector<string> ans = cross_sort_ips(ips);

    // 空格分隔输出
    for (int i = 0; i < (int)ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

题目内容

$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$