软件版本交叉排序

题意

给定 个软件版本号，格式为 a.b.c.d（主版本号.次版本号.修订号.构建号），每个分量都是整数。要求先按版本号从小到大排序，然后按"交叉"顺序输出：最小、最大、次小、次大……依次交替，直到所有版本号输出完毕。

版本号比较规则：先比主版本号，相同则比次版本号，再相同比修订号，最后比构建号。

思路

这道题分两步走：排序 + 重排列。

第一步：排序。 把版本号字符串拆成四个整数，按字典序（先比第一个分量，再比第二个……）排序。这就是最基本的多关键字排序。

第二步：交叉排列。 排好序之后，用双指针从两头往中间收。左指针 lo 从最小端出发，右指针 hi 从最大端出发，交替取值放进结果数组：

  1. 取 sorted[lo]，lo++
  2. 如果 lo <= hi，取 sorted[hi]，hi--
  3. 重复直到 lo > hi

拿样例验证一下：排序后是 1.126.127.128, 3.36.80.34, 35.107.224.55, 80.42.126.88, 101.21.35.63，交叉取就是 1... 101... 3... 80... 35...，和预期输出一致。

复杂度

  • 时间：，排序主导
  • 空间：

代码

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

int main(){
    int n;
    scanf("%d", &n);
    vector<string> vers(n);
    vector<array<int,4>> parsed(n);
    for(int i = 0; i < n; i++){
        char buf[200];
        scanf("%s", buf);
        vers[i] = buf;
        sscanf(buf, "%d.%d.%d.%d", &parsed[i][0], &parsed[i][1], &parsed[i][2], &parsed[i][3]);
    }
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return parsed[a] < parsed[b];
    });
    vector<string> res;
    int lo = 0, hi = n - 1;
    while(lo <= hi){
        res.push_back(vers[idx[lo]]);
        lo++;
        if(lo <= hi){
            res.push_back(vers[idx[hi]]);
            hi--;
        }
    }
    for(int i = 0; i < (int)res.size(); i++){
        if(i) printf(" ");
        printf("%s", res[i].c_str());
    }
    printf("\n");
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] vers = new String[n];
        int[][] parsed = new int[n][4];
        for (int i = 0; i < n; i++) {
            vers[i] = sc.next();
            String[] parts = vers[i].split("\\.");
            for (int j = 0; j < 4; j++) {
                parsed[i][j] = Integer.parseInt(parts[j]);
            }
        }
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        final int[][] p = parsed;
        Arrays.sort(idx, (a, b) -> {
            for (int j = 0; j < 4; j++) {
                if (p[a][j] != p[b][j]) return p[a][j] - p[b][j];
            }
            return 0;
        });
        StringBuilder sb = new StringBuilder();
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            if (sb.length() > 0) sb.append(' ');
            sb.append(vers[idx[lo]]);
            lo++;
            if (lo <= hi) {
                sb.append(' ');
                sb.append(vers[idx[hi]]);
                hi--;
            }
        }
        System.out.println(sb.toString());
    }
}

import sys

def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    vers = input_data[1:n+1]

    def parse(v):
        return tuple(int(x) for x in v.split('.'))

    sorted_vers = sorted(vers, key=parse)

    res = []
    lo, hi = 0, n - 1
    while lo <= hi:
        res.append(sorted_vers[lo])
        lo += 1
        if lo <= hi:
            res.append(sorted_vers[hi])
            hi -= 1

    print(' '.join(res))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const vers = [];
    for (let i = 1; i <= n; i++) vers.push(lines[i]);

    const parse = v => v.split('.').map(Number);

    vers.sort((a, b) => {
        const pa = parse(a), pb = parse(b);
        for (let j = 0; j < 4; j++) {
            if (pa[j] !== pb[j]) return pa[j] - pb[j];
        }
        return 0;
    });

    const res = [];
    let lo = 0, hi = n - 1;
    while (lo <= hi) {
        res.push(vers[lo]);
        lo++;
        if (lo <= hi) {
            res.push(vers[hi]);
            hi--;
        }
    }
    console.log(res.join(' '));
});