package sort;

import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

/**
 * CSDN 排序竞赛
 * @version 2008-06-24 07:31
 */
class TestSort {
  static int MAX = 1000000; // 最大数据量

  static int[] nums = new int[MAX]; // 特意移到类一级，免得他们需要时没有这个

  static Map<Long, String> map = new TreeMap<Long, String>(); // 排序的结果，纳秒为单位了。

  static long seed = 20080623;

  private static void init() {
    Random r = new Random(seed);
    for (int i = 0; i < MAX; i++) {
      nums[i] = r.nextInt(MAX);
    }
  }

  private static String showResult() { // 这里随便选了几个进行排序结果的测试
    return nums[1] + " " + nums[1234] + " " + nums[23456] + " " + nums[67890] + " " + nums[MAX - 1];
  }

  public static void main(String[] args) {
    Random ran = new Random();
    for (int i = 1; i <= 1; i++) { // 此处定义循环测试的次数
      seed = ran.nextInt(999999999);
      test();
    }
    for (String str : map.values()) {
      System.out.print(str);
    }
  }

  public static void test() {
    long begin;
    long end;
    //
    // 测试代码框架开始
    init();
    begin = System.nanoTime();
    sort_JDK(nums);
    end = System.nanoTime();
    map.put((end - begin), String.format("%20s%15d %s\r\n", "sort_JDK=", (end - begin), showResult()));
    // 测试代码框架结束



    // 其它的测试代码将按照顺序逐个放到后面进行测试。
    // 某些方法没有使用我提供的标准调用，造成我手工修改，引起不必要的问题。
    // 请大家查看我测试的完整代码，并根据你的需求进行完善与修改。

   }
  public static int[] sort_JDK(int[] nums) {
    Arrays.sort(nums);
    return nums;
  }
}

import java.util.Random;

public class MarquisSort
{
    private static int[] resultData;
    
    public static void main( String[] args )
    {

        int MAX = 100000;
        int[] nums = new int[ MAX ];
        Random r = new Random( 20080623 );
        for( int i = 0; i < MAX; i++ )
        {
            nums[ i ] = r.nextInt( MAX );
        }
        long begin = System.currentTimeMillis();
        int[] data = sort( nums );
        long end = System.currentTimeMillis();
        System.out.println( ( end - begin ) ); // 以这个时间为标准，越小越好。
    }

    public static int[] sort_vtudiv( int[] nums )
    {
           
        int[] temp = new int[nums.length];
        int max = getMax(temp)+1;
        for(int i:nums)
        {
            temp[i]++;
        }
        int pos=0;
        for (int i=0;i<max;i++)
        {
            if (temp[i]>0)
            {
                for(int l=0;l<temp[i];l++)
                    nums[pos++]=i;
            }
        }
        return nums;
    }
    
    private static int getMax( int[] data )
    {
        int max = 0;
        for( int i=data.length;;i--)
        {
            if( 0!=data[i] )
            {
                max = i;
                break;
                
            }
        }
        return max;
    }
}