完美洗牌问题（2）

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

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    sort(a, a+n);
    for(int i=0;i<n;i++){
        if(i&1 && i!=n-1)
            swap(a[i], a[i+1]);
        printf("%d ", a[i]);
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int modifyIndex(int i, int len);

void reverse(int *arr, int l, int r);

void rotate(int *arr, int l, int m, int r);

void shuffle(int *arr, int l, int r);

void cycles(int *arr, int l, int len, int k);

void heapSort(int *arr, int n);

void downAdjust(int *arr, int i, int n);

void swap(int *arr, int i, int j);

int main(void) {
    int n, *arr;
    scanf("%d", &n);
    arr = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    heapSort(arr, n);
    if (n % 2 == 0) {
        shuffle(arr, 0, n - 1);
        for (int i = 0; i < n; i += 2) {
            swap(arr, i, i + 1);
        }
    } else {
        shuffle(arr, 1, n - 1);
    }
    for (int i = 0; i < n; i++) {
        if (i != 0) printf(" ");
        printf("%d", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

int modifyIndex(int i, int len) {
    return (i * 2) % (len + 1);
}

void reverse(int *arr, int l, int r) {
    while (l < r)
        swap(arr, l++, r--);
}

void rotate(int *arr, int l, int m, int r) {
    reverse(arr, l, m);
    reverse(arr, m + 1, r);
    reverse(arr, l, r);
}

void shuffle(int *arr, int l, int r) {
    int len, base, k, n, mid;
    while (r - l + 1 > 0) {
        len = r - l + 1;
        base = 1;
        k = 0;
        // 得出不超过len且满足3^k-1的最长长度
        while (base * 3 <= len + 1) {
            base *= 3;
            k++;
        }
        n = (base - 1) >> 1;
        mid = l + ((r - l) >> 1);
        rotate(arr, l + n, mid, mid + n);
        cycles(arr, l, base - 1, k);
        l += base - 1;
    }
}

void cycles(int *arr, int l, int len, int k) {
    int pre, cur, tmp;
    for (int i = 0, s = 1; i < k; i++, s *= 3) {
        pre = arr[l + s - 1];
        cur = modifyIndex(s, len);
        while (cur != s) {
            tmp = arr[l + cur - 1];
            arr[l + cur - 1] = pre;
            pre = tmp;
            cur = modifyIndex(cur, len);
        }
        arr[l + cur - 1] = pre;
    }
}

void heapSort(int *arr, int n) {
    for (int i = (n - 2) >> 1; i >= 0; i--) {
        downAdjust(arr, i, n);
    }
    while (n > 1) {
        swap(arr, 0, n - 1);
        downAdjust(arr, 0, n - 1);
        n--;
    }
}

void downAdjust(int *arr, int i, int n) {
    int left = i << 1 | 1;
    while (left < n) {
        int better = (left + 1 < n && arr[left + 1] > arr[left]) ?
                     left + 1 : left;
        if (arr[i] >= arr[better]) break;
        swap(arr, i, better);
        i = better;
        left = i << 1 | 1;
    }
}

void swap(int *arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

// 思路:观察规律就是，如果是有序的数组，那么只要每隔两个数进行交换，那就可以了
// 如果数组长度<=2,那么就不改变
function mysort(a,b){
    if(a>b){
        return 1;
    }else if(a<b){
        return -1
    }else{
        return 0
    }
}
var len=parseInt(readline())
var arr=readline().split(' ').map(Number).sort(mysort);
if(len<=2){
    console.log(arr.join(' '))
}else{
    for(var i=1;i<len;i+=2){
        var tem=arr[i];
        arr[i]=arr[i+1];
        arr[i+1]=tem;
        // 遍历到倒数第二个的时候就可以停了，也有可能到达最后一个
        if(i+1>=len-2){
            break;
        }
    }
    console.log(arr.join(' '))
}

#include <algorithm>
#include <iostream>

using namespace std;

//给定一个数组arr，请将数组调整为依次相邻的数字，总是先<=、再>=的关系，并交替下去。比如数组中有五个数字，调整成[a,b,c,d,e],使之满足a<=b>=c<=d>=e。
//
//输入描述:
//输入包含两行，第一行一个整数n（1 \leq n \leq 10^5）（1≤n≤10 
//5
// ），代表数组的长度,接下来一行n个整数，代表数组arr（1 \leq arr_i \leq 10^9）（1≤arr 
//i
//	
// ≤10 
//9
// ）。
//
//
//输出描述:
//输出一行，代表调整后的数组。
//示例1
//输入
//6
//1 2 3 4 5 6
//输出
//1 3 2 5 4 6
int main() {
    int n;
    cin >> n;
    int right = n / 2;
    int left = n - right;
    int arr[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for (int i = 0; i < right; ++i) {
        cout << arr[i] << " " << arr[left + i] << " ";
    }
    if (left != right) {
        cout << arr[left - 1];
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num.begin(),num.end());
    for(int i = 1;i<n-1;i+=2)
        swap(num[i],num[i+1]);
    for(int i=0;i<n;i++)
        cout<<num[i]<<" ";
    return 0;
}

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        heapSort(arr);
        //奇数数量情况下：
        if((n & 1) != 0) {
            shuffle(arr, 1, arr.length-1);
        }
        //偶数数量情况下：
        else {
            shuffle(arr, 0, arr.length-1);
            for (int i = 0; i < arr.length - 1; i+=2) {
                swap(arr, i, i+1);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb.toString().trim());
    }
    
    /*
    在arr[L...R]上做洗牌，整体策略为：
    假设共2*6=12个数，先在 L1, L2, ..., R3, R4 这8个数上做下标连推，
    然后分别在L5, R5；L6, R6 这两组数上做下标连推，目的是为了使每次做下标连推
    的子数组数量都满足3^k-1. 为了实现下标连推，则必须在之前实现翻转字符串
    比方说在第一次下标连推前，把L5, L6,..., R3, R4左部分设为L5, L6, 有部分设为
    R1..R4, 然后进行翻转
    */
    public static void shuffle(int[] arr, int L, int R) {
        while(R - L + 1 > 0) {
            int len = R-L+1;
            int base = 3;
            int k = 1;
            //计算<=len且距离len最近的，满足(3^k-1)的数
            //也就是找到最大的k，满足3^k <= len+1
            while(base <= (len+1) / 3) {
                base *= 3;
                k++;
            }
            //当前要解决base-1块，一半就是再除以2
            int half = (base-1) / 2;
            //[L...R]的中点位置
            int mid = (L+R) / 2;
            //要旋转的左部分为[L+half...mid], 右部分为arr[mid+1...mid+half]
            //注意，这里arr下标是从0开始
            reversePart(arr, L + half, mid, mid + half);
            //旋转完成后，从L开始算起，长度为base-1的部分进行下标连续推
            cycles(arr, L, base-1, k);
            L += base - 1;
        }
    }
    
    public static void reverse(int[] arr, int L, int R) {
        while (L < R) {
            int tmp = arr[L];
            arr[L++] = arr[R];
            arr[R--] = tmp;
        }
    }
    
    public static void reversePart(int[] arr, int L, int M, int R) {
        reverse(arr, L, M);
        reverse(arr, M+1, R);
        reverse(arr, L, R);
    }
    
    /*
    下标连推，即多米诺骨牌效应，从某一位开始，使其顶掉新位置上的数，再让被顶掉
    的数去顶它的新位置上的数
    若数组长度为2*N == 3^k - 1, 则共有k个多米诺骨牌效应,且出发位置为1，3，9...3^(k-1)
    */
    public static void cycles(int[] arr, int start, int len, int k) {
        for(int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
            int preVal = arr[start + trigger - 1];
            int cur = getNewIndex(trigger, len);
            while (cur != trigger) {
                int tmp = arr[start + cur - 1];
                arr[start + cur - 1] = preVal;
                preVal = tmp;
                cur = getNewIndex(cur, len);
            }
            arr[start + cur - 1] = preVal;
        }
    }
    
    //获得的新位置在数组中第几位
    public static int getNewIndex(int i, int len) {
        if (i <= len / 2)
            return 2 * i;
        else 
            return 2 * (i - len/2) - 1;
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    public static void heapify(int[] arr, int i, int size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int maxIndex = 0;
        while (left < size) {
            maxIndex = left;
            if (right < size && arr[right] > arr[left])
                maxIndex = right;
            maxIndex = arr[maxIndex] > arr[i] ? maxIndex : i;
            if (maxIndex == i)
                break;
            swap(arr, i, maxIndex);
            i = maxIndex;
            left = 2 * i + 1;
            right = 2 * i + 2;
        }
    }
    
    public static void heapSort(int[] arr) {
        for (int i = arr.length-1; i > -1; i--) {
            heapify(arr, i, arr.length);
        }
        for (int i = arr.length-1; i > -1; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }
}