全排序算法的实现

在CSDN上看到了一道笔试题,看到了有人写了实现.

闲来无事,以前也没写过类似的实现,于是我自己也试着写了一个.贴在这里,以备有用的人不时之需.

MAIN 中还写了个测试效率的东东. 把程序中 System.out.print.... 的注释全去掉,就有输出了.

有兴趣的话运行一下吧. *_*

 

package chouy.array;

/**
 * 现在有int sss[] = {4,5,8,9}，写一段程序让程序输出sss这个数组的所有排序！
 * 比如说4,5,8,9
 * 4,5,9,8
 * 4,9,5,8
 * 4,9,8,5等等所有的排序种类，总共应该是24种,这个程序应该怎么编写？谢谢
 */
public class RandomArray<T>
{
    private int kind = 1;
    private StringBuilder sbuf = new StringBuilder(20);

    // 6 楼开始

    private void queue(int[] sss, int[] ss1)
    {
        if (sss.length > 1)
        {
            int[] yyy = new int[sss.length - 1];
            int[] yy1 = new int[ss1.length + 1];
            for (int i = 0; i < sss.length; i++)
            {
                int sum;
                for (int j = 0; j < yyy.length; j++)
                {
                    if (j < i)
                        sum = j;
                    else
                        sum = j + 1;
                    yyy[j] = sss[sum];
                }
                for (int k = 0; k < ss1.length; k++)
                {
                    yy1[k] = ss1[k];
                }
                yy1[yy1.length - 1] = sss[i];
                queue(yyy, yy1);
            }
        }
        else
        {
            sbuf.append("第").append(kind++).append("种: ");
            for (int s : ss1)
                sbuf.append((char) s + "");
            sbuf.append((char) sss[0]);
            // System.out.println(sbuf);

            sbuf = new StringBuilder(20);
        }
    }

    public void taxis(int[] sss)
    {
        kind = 1;
        int[] ss1 = new int[0];
        queue(sss, ss1);
    }
    // 6 楼结束


    // 64 楼程序开始

    public void printallpaixu(int A[], String frontstr)
    {
        int size = A.length;
        if (size == 2)
        {
            // System.out.println(frontstr + " " + A[0] + " " + A[1]);

            // System.out.println(frontstr + " " + A[1] + " " + A[0]);

            return;
        }
        for (int i = 0; i < size; i++)
        {
            String newforntstr = frontstr + " " + A[i];
            printallpaixu(getMinusArray(i, A), newforntstr);
        }
    }

    /* 获得少一个元素的新数组 */
    private int[] getMinusArray(int movepos, int[] oldarray)
    {
        int size = oldarray.length;
        int[] newarray = new int[size - 1];
        for (int i = 0; i < size; i++)
        {
            if (i < movepos)
            {
                newarray[i] = oldarray[i];
            }
            else if (i > movepos)
            {
                newarray[i - 1] = oldarray[i];
            }
        }
        return newarray;
    }
    // 64 楼结束


    // mine begin

    private int[] getSubArray(int[] array, int kickPosition)
    {
        if (array == null || array.length == 0)
            return array;
        int[] copyArray = new int[array.length - 1];
        int posCopyArray = 0;
        for (int posArray = 0; posArray < array.length; posArray++)
        {
            if (posArray == kickPosition)
                continue;
            else
                copyArray[posCopyArray++] = array[posArray];
        }
        return copyArray;
    }

    public void allArrange(int[] array)
    {
        int[] tmp;
        if (array == null || array.length == 0)
            return;
        if (array.length == 1)
        {
            // System.out.println(sbuf.toString() + array[0]);

        }
        else
        {
            for (int i = 0; i < array.length; i++)
            {
                tmp = this.getSubArray(array, i);
                sbuf.append(array[i]);
                allArrange(tmp);
            }
        }
        if (sbuf.length() != 0)
            sbuf.deleteCharAt(sbuf.length() - 1);
    }
    // mine end


    public static void main(String[] args)
    {
        int[] sss = { '1', '2', '3', '4', '5', '6' };
        int times = 100;
        int i;
        RandomArray test = new RandomArray();
        long t1 = System.currentTimeMillis();
        i = times;
        while (i-- > 0)
        {
            test.taxis(sss);
        }
        long t2 = System.currentTimeMillis();
        i = times;
        while (i-- > 0)
        {
            test.allArrange(sss);
        }
        long t3 = System.currentTimeMillis();
        i = times;
        while (i-- > 0)
        {
            test.printallpaixu(sss, "");
        }
        long t4 = System.currentTimeMillis();
        System.out.println(t2 - t1);
        System.out.println(t3 - t2);
        System.out.println(t4 - t3);
        test.allArrange(sss);
    }
}