ac

给定一个数组arr，请将数组调整为依次相邻的数字，总是先<=、再>=的关系，并交替下去。比如数组中有五个数字，调整成[a,b,c,d,e],使之满足`a <= b >= c <= d >= e`。

小1 大1 小2 大2 小3 大3， 类似完美洗牌

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        // 先排序
        Arrays.sort(arr);
        // 特殊处理
        if(n == 1){
            System.out.println(arr[0]);
            return;
        }
        if(n == 2){
            System.out.println(arr[0] + " " + arr[1]);
            return;
        }
        if(n == 3){
            System.out.println(arr[0] + " " + arr[2] + " " + arr[1]);
            return;
        }
        // 按照完美洗牌处理
        if(n % 2 == 0) { // 偶数
            perfectShuffle(arr, n);

            // 要变成小大小 O(n) 移动下元素，要是大小大就不需要了
            int tmp = arr[0];
            for(int i=0;i<n-1;i++){
                arr[i] = arr[i+1];
            }
            arr[n-1] = tmp;
        }else {// 奇数
            perfectShuffle(arr, n-1);
            int tmp = arr[0];
            for(int i=0;i<n-2;i++){
                arr[i] = arr[i+1];
            }
            arr[n-2] = tmp;
            // 最后特殊处理
            swap(arr, n-2, n-1);
        }
        // print
        for(int i=0;i<n-1;i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(arr[n-1]);
    }

    static void reverse(int[] chars, int l, int r) {
        int temp;
        while(l < r) {
            temp = chars[l];
            chars[l] = chars[r];
            chars[r] = temp;
            l++;
            r--;
        }
    }

    static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static void cycle(int[] arr, int startIndex, int n, int firstPos){
        int pre = arr[startIndex + firstPos - 1];
        int firstIndex = firstPos;
        int next = (2 * firstIndex) % (2*n + 1);
        while (next != firstPos){
//            System.out.print(next + " ");
//            swap(arr, startIndex + firstIndex - 1, startIndex + next - 1);
            int tmp =  arr[startIndex + next - 1];
            arr[startIndex + next - 1] = pre;
            pre = tmp;
            next = (2 * next) % (2*n + 1);
        }
        arr[startIndex + firstPos - 1] = pre;
    }

    static void move(int[] arr, int startIndex, int n, int m){
        // startIndex   startIndex + m  startIndex + n
        // startIndex + n   startIndex + n + n - m startIndex + 2n
        reverse(arr, startIndex + m, startIndex + n - 1);
        reverse(arr, startIndex + n, startIndex + n + m - 1);
        reverse(arr, startIndex + m, startIndex + n + m - 1);
    }

    static void perfectShuffle(int[] arr, int len){
        int n = len / 2;
        int startIndex = 0;
        while (n >= 1){
            int k = 0;
            int r = 1;
            while (r - 1 <= 2*n){
                r = r * 3;
                k++;
                if(r-1 == 2*n){
                    break;
                }
            }
            if(r - 1 == 2 * n){ // 刚刚好 3^k - 1
                // 再cycle, 开始位置依次是 3^(k-1)
                int firPost = 1;
                for(int i=0;i<k;i++) {
                    cycle(arr, startIndex, (r - 1) / 2, firPost);
                    firPost *= 3;
                }
                break;
            }else {
                int m = (r/ 3 - 1) / 2;
                k--;
                // 字符串内块移动，三步翻转即可
                move(arr, startIndex, n, m);
                // 再cycle, 开始位置依次是 3^(k-1)
                int firPost = 1;
                for(int i=0;i<k;i++) {
                    cycle(arr, startIndex, m, firPost);
                    firPost *= 3;
                }
                // 最后递归
                startIndex = startIndex + r/3 - 1;
                int left = 2*n - 2*m;
                n = left / 2;
            }
        }
    }

}
/*
6
1 2 3 4 5 6

1 3 2 5 4 6

3
1 2 3

1 3 2
*/