求一个算法

Question

/*
         You need to sort an array of integers by repeatedly reversing  the order of the first several elements of it.         For example, to sort [12,13,11,14], you need to  reverse the order of the first two (2)
         elements and get [13,12,11,14] and then reverse the order of the first three (3)
         elements and get [11,12,13,14]         The method should return the shortest(!) possible list of integers corresponding to the required reversals.
         For the previous example, given an array [12,13,11,14]
         the method should return a list with Integers 2 and 3.
        */
 public static List<Integer> getReversalsToSort(int[] a)

Answer 1

按照题目要求，假设有个数组：
1 2 6 3 4 5
因为每次都必须 by repeatedly reversing  the order of the first several elements， 所以最后，6 一定是在最后的位置上，而要把6 reverse到最后的位置上，唯一的办法是先把6 放在第一个位置上，然后revers整个数组。 也就是倒数第二次的数组是：
6 ? ? ? ? ?
倒数第三次的数组要是 6 5 4 3 2 1就最理想了
但是这样肯定就互相矛盾了： 1要放在最后就意味着它最初在第一个，那就意味着6原来在最后....成蛋和鸡的问题了。一种做法是先把最大的跳出来，然后倒推：
1 2 6 3 4 5 ==> 
revers 3 ==> 6 2 1 3 4 5
revers 6 ==> 5 4 3 1 2 6
revers 5 ==> 2 1 3 4 5 6
revers 2 ==> 1 2 3 4 5 6
出是出来了，可是，怎么证明这个是 the shortest(!) possible list ？

Answer 2

按照上面说的，代码如下
    public static void main(String[] args) {
        System.out.println(sort(new int[] {3,4,5,2,6,1}));
    }    private static List<Integer> sort(int[] pIs) {
        List<Integer> result = new ArrayList<Integer>();
        int[] tgtArray = pIs.clone();
        Arrays.sort(tgtArray);
        dumpArray(pIs);
        
        for(int tgtPos = pIs.length-1; tgtPos >=0; tgtPos--){
            int tgtNum = tgtArray[tgtPos];
            if (pIs[tgtPos] == tgtNum) {
                continue; // Already in correct place, jump this one.
            }
            int curPos = findInArray(pIs,tgtNum);
            if (curPos == 0){
                result.add(tgtPos+1);
                reverseArray(pIs, tgtPos);
            }else{
                result.add(curPos+1);
                reverseArray(pIs, curPos);
                result.add(tgtPos+1);
                reverseArray(pIs, tgtPos);
            }
        }
        return result;
    }    private static void reverseArray(int[] pIs, int pTgtPos) {
        System.out.print("DEBUG: reverse "+(pTgtPos+1)+" : ");
        for(int i = 0; i <= pTgtPos/2;i++){
            int a = pIs[i];
            pIs[i] = pIs[pTgtPos-i];
            pIs[pTgtPos-i] = a;
        }
        dumpArray(pIs);
    }    private static int findInArray(int[] pIs, int pTgtNum) {
        for(int i=0;i<pIs.length;i++){
            if (pIs[i] == pTgtNum){
                return i;
            }
        }
        return -1;
    }    private static void dumpArray(int[] pTgtArray) {
        for(int i: pTgtArray){
            System.out.print(i+" ");
        }
        System.out.println();
    }

Answer 3

运行结果
3 4 5 2 6 1 
DEBUG: reverse 5 : 6 2 5 4 3 1 
DEBUG: reverse 6 : 1 3 4 5 2 6 
DEBUG: reverse 4 : 5 4 3 1 2 6 
DEBUG: reverse 5 : 2 1 3 4 5 6 
DEBUG: reverse 2 : 1 2 3 4 5 6 
[5, 6, 4, 5, 2]

Answer 4

clariones 的想法跟我一致，可是怎么知道他是最短的list?如果每次把最大的先兆出来，那直接冒泡排序好了，还省了去颠倒。所以我想这应该不是出题人的意思。ddyouyue能不能继续解释一下，我感觉不是插入排序呀。大家继续动脑子吧。

Answer 5

/**
 *      1,检查是否排好了序
 * 2,找到最大的
 * 3,交换最大的到最前面
 * 4,交换最大的到最后面
 * 5, TO 1(但是缩小范围,最后面排好了的就不用再排了).
 *  
 */
public class ReverseSort {

public static void main(String[] args) {
int src[] = {12,13,11,14};
int test[] = {4,5,0,2,13,6};
getReversalsToSort(src);
getReversalsToSort(test);
}

public static void getReversalsToSort(int[] src){
int wide = src.length;
while(!checkRs(src)){
int reverseLen = findMaxIdx(src,wide);
if(reverseLen != wide - 1){
if(reverseLen != 0){
reverseArray(src,reverseLen + 1);
for(int i : src)
System.out.print(i + " ");
System.out.println();
}

reverseArray(src,wide);
for(int i : src)
System.out.print(i + " ");
System.out.println();
}else{
wide--;
}
}
} //抄了二楼一些
private static void reverseArray(int pIs[],int pTgtPos){
for(int i = 0; i < pTgtPos/2;i++){
            int a = pIs[i];
            pIs[i] = pIs[pTgtPos - i - 1];
            pIs[pTgtPos - i - 1] = a;
        }
}

private static boolean checkRs(int src[]){
for(int idx = 1; idx < src.length; idx++){
if(src[idx] < src[idx - 1])
return false;
}
return true;
}

private static int findMaxIdx(int src[],int wide){
int max = src[0];
int pos = 0;
for(int idx = 1; idx < wide; idx++){
if(src[idx] > max){
max = src[idx];
pos = idx;
}
}
return pos;
}
}
结果:
13 12 11 14 
11 12 13 14 
13 2 0 5 4 6 
6 4 5 0 2 13 
2 0 5 4 6 13 
5 0 2 4 6 13 
4 2 0 5 6 13 
0 2 4 5 6 13
the method should return a list with Integers 2 and 3. 就没做了