分析： 题目虽然新规定了排列规则， 但是还是存在大小顺序的， 所以我们可以先对数组先进行排序， 然后再将排好序的数组重新按照规则再组合

代码如下：

package com.wenj.test;

/*
 * 给定一个数组input[] ，如果数组长度n为奇数，
 * 则将数组中最大的元素放到 output[] 数组最中间的位置，
 * 如果数组长度n为偶数，
 * 则将数组中最大的元素放到 output[] 数组中间两个位置偏右的那个位置上，
 * 然后再按从大到小的顺序，依次在第一个位置的两边，
 * 按照一左一右的顺序，依次存放剩下的数。
 * 例如：
 *  input[] = {3, 6, 1, 9, 7}  
 *  output[] = {3, 7, 9, 6, 1};
 *  input[] = {3, 6, 1, 9, 7, 8}   
 *  output[] = {1, 6, 8, 9, 7, 3}
 * */

public class TestNewSort {

    public static void main(String args[]){
        int input[] = {3, 6, 1, 9, 7, 8};  
        TestNewSort tn = new TestNewSort();
        int output[] = tn.getNewSort(input);
        for(int i=0; i< output.length; i++){
            System.out.print(output[i] + " ");
        }
    }
    
    public int[] getNewSort(int[] input){
        int[] newArr = input;
        for(int i=0; i<newArr.length; i++){
            for(int j=0; j<newArr.length-1-i; j++){
                if(newArr[j]<newArr[j+1]){
                    int temp = newArr[j];
                    newArr[j] = newArr[j+1];
                    newArr[j+1] = temp;
                }
            }
        }
        
        int[] temp = new int[newArr.length];
        temp[newArr.length/2] = newArr[0];
        int high = newArr.length/2 + 1;
        int low = newArr.length/2 - 1;
        for(int i=1; i<newArr.length; ){
            if(low >=0){//依次将大的元素排在左边
                temp[low] = newArr[i];
                low--;
                i++;
            }
            
            if(high<newArr.length){//依次将第二大的排在右边
                temp[high] = newArr[i];    
                high++;
                i++;
            }
        }
        
        return temp;
    }
}