import java.util.Arrays;
import java.util.Random;

/**
 * 有N个大小不等的自然数（1--N），请将它们由小到大排序。 要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
 * 
 * @author chouy
 */
public class SortArrayFrom1toN extends Base
{
    public static int N = 5000;
    public static Random random = new Random();

    public static void main(String[] args)
    {
        int[] is = new int[N];
        for (int i = 0; i < is.length; i++)
        {
            is[i] = i;
        }
        // 打乱顺序
        int tmp;
        for (int i = 0; i < is.length; i++)
        {
            int j = random.nextInt(N);
            tmp = is[i];
            is[i] = is[j];
            is[j] = tmp;
        }
        info(Arrays.toString(is));
        info(Arrays.toString(new SortArrayFrom1toN().sort(is)));
    }

    /**
     * 用交换的方法进行排序.<br>
     * 交换方法:交换回来的数如果不应该在当前位置,则再把它与它应该在的位置交换
     * 
     * @param array
     * @return
     */
    public int[] sort(int[] array)
    {
        int exchangeTimes = 0; // 比较计数器
        int tmp;
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] != i)
            {
                tmp = array[array[i]];
                array[array[i]] = array[i];
                array[i] = tmp;
                i--;
                exchangeTimes++;
            }
        }
        debug("exchangeTimes = " + exchangeTimes);
        return array;
    }
}

------解决方案--------------------