高矮排序

刷题 华为机试

题目：现在有一队小朋友，他们高矮不同，我们以正整数数组表示这一队小朋友的身高，如数组{5,3,1,2,3}。我们现在希望小朋友排队，以“高”“矮”“高”“矮”顺序排列，每一个“高”位置的小朋友要比相邻的位置高或者相等；每一个“矮”位置的小朋友要比相邻的位置矮或者相等；要求小朋友们移动的距离和最小，第一个从“高”位开始排，输出最小移动距离

例如，在示范小队{5,3,1,2,3}中，{5, 1, 3, 2, 3}是排序结果。{5, 2, 3, 1, 3} 虽然也满足“高”“矮”“高”“矮”顺序排列，但小朋友们的移动距离大，所以不是最优结果。

移动距离的定义如下所示：第二位小朋友移到第三位小朋友后面，移动距离为1，若移动到第四位小朋友后面，移动距离为2；

难度：*

输入描述：排序前的小朋友(小朋友<100个)，以英文空格的正整数：4 3 5 7 8
输出描述：排序后的小朋友，以英文空格分割的正整数：4 3 7 5 8，只有5和7交换了位置，最小移动距离都是1.

示例1：
输入：4 1 3 5 2
输出：4 1 5 2 3

示例2：
输入：1 1 1 1 1
输出：1 1 1 1 1

示例3：
输入：xxx
输出：[]
说明：出现非法参数情况，返回空数组

链接：http://www.amoscloud.com/?p=3312

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int[] h = new int[s.length];
        for (int i=0; i<s.length; i++){
            if (s[i].matches("[0-9]+")){//匹配数字
                h[i] = Integer.parseInt(s[i]);
            } else{
                System.out.println("[]");
                return;
            }
        }
        for (int i=0; i<h.length-1; i++){
            if (i%2==0 && h[i]<h[i+1]){//偶数索引位 高
                swap(h, i, i+1);
            }
            if (i%2==1 && h[i]>h[i+1]){//奇数索引位 矮
                swap(h, i, i+1);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i : h) {
            sb.append(i).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
    private static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}