【竞赛】排序算法的最快实现-继续

Question

由于早上帖子不能访问，我只能忍痛结掉了。并根据现有的成绩分配了积分。澄清一下这个竞赛的目的，是为了大家共同拿到几个排序的好的算法，注意是几个，而不是一个。
在不同的情况下，各个算法的表现是不同的。新的测试代码可以自行定义测试的次数和随机的种子。 可以对测试结果自动排序。
下面给出新的测试代码框架。完整代码太长，需要的请到这里获取， 其中包括已经在另一个帖子给出算法的测试。 http://blog.zhaoxq.java2000.net/v16 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;
  }
}
请大家整理好自己的算法帖子，命名方法为
public static int[] sort_${CSDN_USERNAME}(int[] nums) 
比如
public static int[] sort_java2000_net(int[] nums) 
public static int[] sort_talent_marquis(int[] nums) {

Answer 1

原始帖子链接如下！
http://topic.csdn.net/u/20080623/14/23ab6317-1179-4c24-bb41-39b2d00697d5.html

Answer 2

单纯的数组排序似乎意义不大，
以前也专门研究过一段时间，
发现排序效率和给定的序列初始顺序有很大的关系，
而且对于中小规模序列，效率并没有实质性的提高，
例如十万个数据（对于中小规模的系统），
如果最好的排序算法与最差的算法差了100ms，
其实对于用户来说几乎毫无意义。
我在实际应用中最关心按索引排序，
例如有10000个学生Stru的实例，首先有个学号排序（id，这可以从数据库中通过sort获得），
后来要按照他们年龄或者身高排序，同时要记录原有的学号顺序。

Answer 3

下面公布几个排名前5名的算法  public static int[] sort_sagezk2(int[] nums) {
    final int LEN = nums.length;
    int i, j, t, p;
    int[] temp = new int[LEN];
    for (i = 0; i < LEN;) {
      temp[nums[i++]]++;
    }
    for (i = 0, p = 0; i < LEN; ++i) {
      if ((t = temp[i]) == 0)
        continue;
      for (j = 0; j < t; ++j) {
        nums[p++] = i;
      }
    }
    return nums;
  }  public static int[] sort_scf37(int[] nums) {
    int max = nums.length;
    int i, j;
    int[] temp = new int[max];
    for (i = 0; i < max;) {
      temp[nums[i++]]++;
    }
    int pos = 0;
    for (i = 0; i < max; ++i) {
      for (j = 0; j < temp[i]; ++j) {
        nums[pos++] = i;
      }
    }
    return nums;
  }  public static int[] sort_lwouyang(int[] nums) {
    int max = MAX / 2; // 不会猜不中吧?! 真猜不中的话立马去买彩票!! ^_^
    int[] temp = new int[nums.length];
    for (int i : nums) {
      temp[i]++;
      if (i > max)
        max = i;
    }
    int pos = 0;
    for (int i = 0; i <= max; i++)
      for (int l = 0; l < temp[i]; l++)
        nums[pos++] = i;
    return nums;
  }  public static int[] sort_john_sheep(int[] nums) {
    int max = getMax_john_sheep(nums) + 1;
    int[] temp = new int[max];
    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_john_sheep(int[] data) {
    int max = 0;
    for (int i : data) {
      if (i > max) {
        max = i;
      }
    }
    return max;
  }  public static int[] sort_roofalison(int[] nums) {
    // 您的排序代码放在这里啦
    int[] flag = new int[nums.length + 1];
    for (int i = 0; i < nums.length; ++i)
      ++flag[nums[i]];
    int ct = 0;
    for (int i = 0; i < nums.length; ++i)
      while (flag[i]-- > 0)
        nums[ct++] = i;
    return nums;
  }

Answer 4

改的john_sheep的,恐怕他的很难超越了.
改的好像还没以前的快,数分布的太均匀了.........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;
    }
}

Answer 5

int max = nums.length;
这句这么写是有风险的，现在属于非稀疏排序情况，也就是在n个数字中随机取n个数字如果是稀疏的，比如说在1000万个数字中随机去10万个或者100万个数字，将能取到的数字中的最大值定义为100万或者10万，肯定会出问题的。

Answer 6

不好意思，态度不太好，向楼主和大家郑重认错，写了代码出来。 
核心思路是准备20080623个桶，把数字丢进去，再顺次取出来，复杂度O(n) 
C# code
using System;namespace ConsoleApplication1
{
    class Program
    {
        static int MaxRange = 20080623;
        static void Main(string[] args)
        {
            Test(10*10000);
            Console.Read();
            Test(100*10000);
            Console.Read();
            Test(1000*10000);
            Console.Read();
        }
        public static void Test(int MAX)
        {           
            int[] nums = new int[MAX];
            Random r = new Random(MaxRange);
            for (int i = 0; i < MAX; i++)
            {
                nums[i] = r.Next(MAX);
            }
            long begin = System.DateTime.Now.Ticks;
            Sort(nums);
            long end = System.DateTime.Now.Ticks;
            Console.WriteLine("总共" + MAX/10000 + "万数据，用时" + System.TimeSpan.FromTicks(end - begin).Milliseconds + "豪秒");           
        }        public static void Sort(int[] a)
        {            int[] p = new int[MaxRange + 1];
            for (int i = 0; i <= MaxRange; i++)
            {
                p[i] = 0;
            }
            for (int i = 0; i <a.Length; i++)
            {
               p[a[i]]++;
            }
            for (int i = 0, j = 0; i <= MaxRange; i++)
            {
                while (p[i] > 0)
                {
                    a[j++] = i;
                    p[i]--;
                }
            }
             
        }
    }
}10万需要187毫秒 
100万需要250毫秒 
1000万需要984毫秒 可见需要时间和楼主给定的20080623范围有关，和数据量没关系。

Answer 7

理论上，任何排序都可以在时间复杂度为O（n）,空间复杂度为O(1)。

Answer 8

闻道有先后，树业有专攻。 
被鄙视不要紧，缺啥补啥，建议看看《算法导论》，先吸取前人的成果，我敢鄙视你是因为我站在巨人的肩膀上。 
鄙视是客观的，即使我不鄙视你，也会有人鄙视你。 看看下边的东东，就知道了，鄙视其实是轻微的，在ACM国际比赛中失败才是真正丢脸的事情。 
一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的 
，主要时间是花在思考算法上，不是花在写程序与debug上。  
下面给个计划你练练： 
  
第一阶段： 
    练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码， 
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打 
出来.  
1.最短路(Floyd、Dijstra,BellmanFord)  
2.最小生成树(先写个prim,kruscal要用并查集，不好写)  
3.大数（高精度）加减乘除  
4.二分查找. (代码可在五行以内)  
5.叉乘、判线段相交、然后写个凸包.  
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)  
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.  
8. 调用系统的qsort, 技巧很多，慢慢掌握.  
9. 任意进制间的转换 第二阶段： 
    练习复杂一点，但也较常用的算法。  
如：  
1. 二分图匹配（匈牙利），最小路径覆盖  
2. 网络流，最小费用流。  
3. 线段树.  
4. 并查集。  
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp  
6.博弈类算法。博弈树，二进制法等。  
7.最大团，最大独立集。  
8.判断点在多边形内。  
9. 差分约束系统.  
10. 双向广度搜索、A*算法，最小耗散优先. 第三阶段： 
    前两个阶段是打基础，第三阶段是锻炼在比赛中可以快速建立模型、想新算法 
。这就要平时多做做综合的题型了。  
1. 把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。  
2. 平时扫扫zoj上的难题啦，别老做那些不用想的题.(中大acm的版主经常说我挑简单的来 
做:-P )  
3. 多参加网上的比赛，感受一下比赛的气氛，评估自己的实力.  
4. 一道题不要过了就算，问一下人，有更好的算法也打一下。  
5. 做过的题要记好 :-)    

Answer 9

看来大家想法都是一样的，都是利用整数与平均分布这两个特性。
俺也想到了，就是动作慢了点。我稍稍测试了一下：
cpu 的 / * + -      最耗时，
其次是 内存的变量赋值   耗时，
其次是 比较两个整数
然后是   ++  --  
再然后是 分配内存楼上前5名的算法都是一样的，有一个共同的特性：计算非常少，赋值次数很少（2n，无法避免的赋值次数）……俺是想不到更快的方法了，关注中，说不定有个牛人看懂了random.nextInt();然后又找到了一个很简单的表达式，直接把值一个个赋给原数组了。

Answer 10

声明：我那个基于n个人的改进算法不参赛，纯属为了精益求精。见 sort_sagezk2。希望还有更快的出现，期待。
另外我所知的改进顺序是：
... -> talent_marquis -> john_sheeping -> SageZk -> scf37 -> SageZk -> ...
如果有遗漏的请楼下回复。

Answer 11

小狼你看错啦那个20080623是产生随机数的种子用的种子，平常都是用System.currentTimeMillis();用来获取伪随机数的。真正的取值范围是MAX，也就是10万是10万，100万是100万，1000万是1000万我说你的算法也不该这么慢么。老紫竹给出的那五个算法，百万数量级都是在100毫秒左右的（因为取值范围只到100万，没有20080623那么多）。

Answer 12

我有一个改进思路，对应稀疏随机数的情况，就是说，先从这个随机数组中随机取出n个数，取平均值再x2作为最有可能的最大值赋给max这样可以减少对max的比较次数，不知可行否？

Answer 13

小弟不才,没写代码,只测试了代码
(只测试时间是1字头的最快的几个)
经测试,
sort_sagezk2
sort_scf37
sort_roofalison
sort_john_sheep
sort_lwouyang
中,只有sort_john_sheep是正确的,其它的都有数组越界
测试数组:
int[] nums = new int[]{45,1,97,25,10,37,5,68};
初步分析原因, 在LZ给出的数组中, nums.length 为:
static int MAX = 1000000;
而数数组中的最大元素为:
Random r = new Random(seed); 
    for (int i = 0; i < MAX; i++) { 
      nums[i] = r.nextInt(MAX); 
    }
只能为:999999当数组中最大元素大于数组长度时,
上述不正确的算法就会数组越界

Answer 14

      sort_sagezk2=      117224116 0 1248 23498 67876 999999
        sort_scf37=      117857716 0 1248 23498 67876 999999
    sort_roofalison=      124729539 0 1248 23498 67876 999999
    sort_john_sheep=      144508869 0 1248 23498 67876 999999
      sort_lwouyang=      145016475 0 1248 23498 67876 999999
    sort_joneyonly3=      292130704 0 1248 23498 67876 999999
    qSor_hmsuccess=      329151610 0 1248 23498 67876 999999
      sort_preferme=      333201846 0 1248 23498 67876 999999
          sort_JDK=      344957250 0 1248 23498 67876 999999
    sort_OXFORD_216=      350317149 0 1224 27373 69355 999999
        sort_B_Lee2=      358643906 0 1248 23498 67876 999999
    sort_J_Factory=      371528504 0 1248 23498 67876 999999
        sort_sagezk=      372204848 0 1248 23498 67876 999999
sort_talent_marquis=      392380038 0 1248 23498 67876 999999
  quickSort_jdlsfl=      413720459 0 1248 23498 67876 999999
    sort_joneyonly2=      451753505 0 1248 23498 67876 999999
    sort_hmsuccess2=      531078670 417157 975013 397974 608759 371602
  sort_geyunfei_hit=      713468611 0 1248 23498 67876 999999
    sort_joneyonly=    1121522149 0 1248 23498 67876 999999
sort_aunty_flybird=    1209051150 0 1248 23498 67876 999999

Answer 15

C# code 
using System; namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static int MaxRange = 20080623; 
        static void Main(string[] args) 
        { 
            Test(10*10000); 
            Console.Read(); 
            Test(100*10000); 
            Console.Read(); 
            Test(1000*10000); 
            Console.Read(); 
        } 
        public static void Test(int MAX) 
        {          
            int[] nums = new int[MAX]; 
            Random r = new Random(MaxRange); 
            for (int i = 0; i < MAX; i++) 
            { 
                nums[i] = r.Next(MAX); 
            } 
            long begin = System.DateTime.Now.Ticks; 
            Sort(nums); 
            long end = System.DateTime.Now.Ticks; 
            Console.WriteLine("总共" + MAX/10000 + "万数据，用时" + System.TimeSpan.FromTicks(end - begin).Milliseconds + "豪秒");          
        }         public static void Sort(int[] a) 
        {             int[] p = new int[MaxRange + 1]; 
            for (int i = 0; i <= MaxRange; i++) 
            { 
                p[i] = 0; 
            } 
            for (int i = 0; i <a.Length; i++) 
            { 
              p[a[i]]++; 
            } 
            for (int i = 0, j = 0; i <= MaxRange; i++) 
            { 
                while (p[i] > 0) 
                { 
                    a[j++] = i; 
                    p[i]--; 
                } 
            } 
            
        } 
    } 
} 
10万需要187毫秒 
100万需要250毫秒 
1000万需要984毫秒 

Answer 16

superdullwolf 的算法目前排名第四       sort_sagezk2=      714360345 0 1231 23482 67805 9999998
    sort_roofalison=      730196436 0 1231 23482 67805 9999998
         sort_scf37=      749415637 0 1231 23482 67805 9999998
      sort_lwouyang=      768712224 0 1231 23482 67805 9999998
 sort_superdullwolf=      793523199 0 1231 23482 67805 9999998
    sort_john_sheep=      797477612 0 1231 23482 67805 9999998前几名的排序经常有微小变化。

Answer 17

请用下面数组测试,谢谢
int[] nums = new int[] { 45, 1, 97, 25, 10, 37, 5, 68 };

Answer 18

请大家用下面数组测试,谢谢
int[] nums = new int[] { 45, 1, 97, 25, 10, 37, 5, 68 };
我之前有回复说发现错误,大家测试下

Answer 19

C# code 
using System; namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static int MaxRange = 20080623; 
        static void Main(string[] args) 
        { 
            Test(10*10000); 
            Console.Read(); 
            Test(100*10000); 
            Console.Read(); 
            Test(1000*10000); 
            Console.Read(); 
        } 
        public static void Test(int MAX) 
        {          
            int[] nums = new int[MAX]; 
            Random r = new Random(MaxRange); 
            for (int i = 0; i < MAX; i++) 
            { 
                nums[i] = r.Next(MAX); 
            } 
            long begin = System.DateTime.Now.Ticks; 
            Sort(nums); 
            long end = System.DateTime.Now.Ticks; 
            Console.WriteLine("总共" + MAX/10000 + "万数据，用时" + System.TimeSpan.FromTicks(end - begin).Milliseconds + "豪秒");          
        }         public static void Sort(int[] a) 
        {             int[] p = new int[MaxRange + 1]; 

//多余代码，删除后性能大幅提高。
            for (int i = 0; i <= MaxRange; i++) 
            { 
                p[i] = 0; 
            }
 
            for (int i = 0; i <a.Length; i++) 
            { 
              p[a[i]]++; 
            } 
            for (int i = 0, j = 0; i <= MaxRange; i++) 
            { 
                while (p[i] > 0) 
                { 
                    a[j++] = i; 
                    p[i]--; 
                } 
            } 
            
        } 
    } 
} 

Answer 20

公布最新的测试结果，1000万数据，随机测试3组，时间累加一起排序sort_sagezk2         6041212780
sort_john_sheep      7315177768
sort_superdullwolf  14449086125
sort_joneyonly3     18909339037
qSor_hmsuccess      22572684797
sort_J_Factory      24048440793
sort_lwouyang       24651375803
sort_roofalison     25412977627
sort_scf37          26693526971
sort_B_Lee2         33814811660
sort_talent_marquis 81382489116

Answer 21

To hanjun1024 
恩，那几行代码的确没意义，因为C#默认数组就是0的，删除后省去了循环。
不过这样不会引起复杂度增加，因为O(n+n)=O(n)
都是同一个复杂度所以其他差别都不算什么。
老紫竹要不再试验下，呵呵

Answer 22

算法局限性太大了！
也就是说针对性太强了！
从数组的生成方式来看，数组中的元素都是非负数且最大元素要小于数组长度
所以有算法要根据数据特征来定了，因此所谓的快速、归并、二分 ...都不在是
最优的了比赛的这个排序数据规律性，局限性都太强了
之所以那几位排序的速度快，就是因为利用了数据的高度规律性，其实程序利用了这个规律，
根本就不需要机器太多的动作吗，时间当然少了分析一个算法的思想吧： public static int[] sort_sagezk2(int[] nums) {
    final int LEN = nums.length;
    int i, j, t, p;
//声明一个同样大小的数组，来记录要排序数组元素的规律
    int[] temp = new int[LEN];
//把要排序的数组的规律性统统记录下来
//是这样记录的：我就假设要排序的数组nums是{2,0,0,0,1}     for (i = 0; i < LEN;) {
      temp[nums[i++]]++;
    }
//那么记录nums数组元素规律性的数组temp经过for循环以后就是{3, 1, 1, 0, 0}
//首先说一下temp的数组元素以及下标的含义：
//temp数组 的第0个元素是3  含义是：0这个元素在nums中出现了3次
//同理 1这个元素在nums中出现了1次 2这个元素在nums中出现了1次 3，4这两个元素在nums中出现了0次
//好友一个就是nums元素在temp中是以数组下标的形式存在的，天生已经排序
//所以，只需根据这个规律赋值nums数组就OK了，根本没有涉及到什么交换呀，排序呀
//说白了  整个排序的时间就是两次数组赋值花费的时间，靠，怎么会用那么长时间啊
    for (i = 0, p = 0; i < LEN; ++i) {
      if ((t = temp[i]) == 0)
        continue;
      for (j = 0; j < t; ++j) {
        nums[p++] = i;
      }
    }     return nums;
  }

Answer 23

/*
 * 运行方式：java -Xms512m -Xmx512m YourMainClassName
 * 优化路径：talent_marquis -> john_sheeping -> SageZk#1 -> scf37 -> SageZk#2 -> SageZk#3
 */
public static int[] sort_sagezk_3(int[] nums) {
final int LEN = nums.length;
int i, t, p;
int[] temp = new int[LEN];
for (i = 0; i < LEN;) {
temp[nums[i++]]++;
}
for (i = 0, p = 0; i < LEN; ++i) {
if ((t = temp[i]) == 0) continue;
t += p;
while (p < t) nums[p++] = i;
}
return nums;
}

Answer 24

怎么优化都得
至少花费两次数组赋值的时间程序的本质就是没有排序吗你给两个 10 万数组赋值 还要花费 15 毫秒
如果你的算法思想不变的话 你的极限就是 15 ms 了，更何况你的赋值过程中的有很多次判断，所以说 不可能达到 15ms 了

Answer 25

但注意是 LEN ++i 没用 nums.length i++ 细节上的改动节省的时间积累多了也是很可观的。

Answer 26

耍点小花招,应该可以更快的.
请楼主再试试.
  public static int[] sort_john_sheep(int[] nums) {   
    int max = getMax_john_sheep(nums) + 1;   
    byte[] temp = new byte[max];   
    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_john_sheep(int[] data) {   
    int max = 0;   
    for (int i : data) {   
      if (i > max) {   
        max = i;   
      }   
    }   
    return max;   
  }   

Answer 27

算法和数据结构的核心就三类思想： 
1，顺序暴力 
2，二分 
3，桶（哈希） 
这个就是桶的思想,牺牲空间换取时间的 举例说：
假设你们班级有30个人，假设按照成绩高低已经把试卷排列好了，你想找出数学成绩在75分的人。第一种办法，就是简单的顺次查找，找到就退出。复杂度O(N)第二种办法，把试卷分两罗，大概在中间那张如果小于75分，就把上边的再分两罗再执行上边步骤，按照这个办法找到为止。
（每次输入范围是上次的一半，递归，这也叫分治算法）复杂度O(logN)第三种办法，假设你有100个编号的桶，你摆放的时候，直接把试卷丢到相应的编号的桶里，这样你一下就找到了试卷。复杂度O(1)
所有的算法都可以最终演变为为查找和排序，排序相当与查找*N。
三种思路下查找的复杂度分别是O(N),O(logN),O(1)。
排序的复杂度分别是O(N*N),O(N*logN),O(N)。掌握这些，数据结构和算法的整体核心思路就有了，所有问题都是从这里衍生出去的。

Answer 28

数组排序算法已经研究几十年了，公认最快的是时间复杂度为 n*log n，空间复杂度为0的算法，
你们有可能讨论出比这快的吗？

Answer 29

版主,我的这个代码,试了一下,感觉存在明显的问题,就是显示结果不唯一,或者不准确.能否讨论一下原因?(而且还存在,第一个方法已经排序完成,第二个方法排序已经排好的数组,的问题.)
只给出一个方法,其他代码不变.
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()));
    // 测试代码框架结束     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()));
   
    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()));
         // 其它的测试代码将按照顺序逐个放到后面进行测试。
    // 某些方法没有使用我提供的标准调用，造成我手工修改，引起不必要的问题。
    // 请大家查看我测试的完整代码，并根据你的需求进行完善与修改。    }

Answer 30

To:r_swordsman 我们都在讨论O(N)的复杂度，你搞一个“公认最快的是时间复杂度为 n*log n”
N < N*Log N
你不会不知道吧。应该是：数组排序算法已经研究几十年了，公认最快的是时间复杂度为O(n) ，空间复杂度为O(1)的算法.记住了，不要搞错！

Answer 31

我把桶算法给出，看看有没有优化，可能写的不好，望大家多多包含，关键是学习算法思想。package temporary;import java.util.Random;public class BuckSort {

    static int MAX = 100000;
    static int BUCKNUM = 10;    //桶的个数
    static int INDEX = 3;       //划分因子
    static int[] cursor = new int[BUCKNUM];
    static int[][] bucket = new int[BUCKNUM][MAX];//其实bucket应该用链表来做，
    
    public static void main(String[] args) {
     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.nanoTime();
        
        for(int i=1; i<=INDEX; ++i)
        {
         Insert(i,nums);
         CpytoArray(nums);
        }
        long end = System.nanoTime();
        System.out.println((end - begin)); // 以这个时间为标准，越小越好。
     }
    
    
    static int getbuckPos(int data,int digit)
    {
     int temp = (int) Math.pow(INDEX, digit-1);
     if(data>temp)
     {
     return (data%temp)/temp;
     }
return 0;
    }
    
    static void Insert(int digit,int[] data)
    {
     int digitnum =0;
      for(int i=0; i<MAX; ++i)
      {
       digitnum=getbuckPos(data[i],digit);
       bucket[digitnum][cursor[digitnum]]=data[i];
       cursor[digitnum]++;
      }       
    }
    static void CpytoArray(int[] data)
    {
      updateB();
     int NumsCpyed=0;
     for(int i=0; i<BUCKNUM; ++i)
     {
      for(int j=0; j<cursor[i]; ++j)
      {
      data[NumsCpyed++]=bucket[i][j];
      }
      cursor[i]=0;
     }
    }    static void updateB()
    {
     for(int j=0;j<BUCKNUM;++j)
     { 
   bucket[j] = sort(bucket[j]);    }
    }
    public static int[] sort( int[] nums ){ 
        int max = getMax(nums)+1; 
        int[] temp = new int[max]; 
          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 ){ 
            if( i > max ){ 
                max = i; 
            } 
        } 
        return max; 
    }
}

Answer 32

关于写算法这方面。印度程序员就不错,用最基本的算法　写每个人都能看懂的Code
而不会这么刻意去写高深的代码段，仅仅去完成一个很简单的算法

Answer 33

我写错了.for( int i=data.length-1;;i--)

Answer 34

这位大哥怎么还用for(xxx : xxx)前一个贴我都提醒你啦   你改成for(xxx ; xxx ; xxx) 试试按你的代码在我机器上运行100万个数排序结果是 109ms
我只把你代码中的for语句改一下，100万个数排序结果是 31ms不信你自己试试

Answer 35

呵呵，多谢
其实sort_sagezk2已经做出了优化，当时我就没有再改动。
一会我也给改了。提高一点是一点。

Answer 36

嘎嘎  我是新手  前几天才知道for(xxx : xxx) 内部是怎么工作的  知道他慢快了可不是一点啊  1000万个数我测试不了  一测试就内存不够了从109ms到31ms  提升好多呢我用快速排序测10万个数是31ms
你的代码改过后测100万个数是31ms   
飞跃了 

Answer 37

请注意 init 在测试框架里面的。 每个新的都会重新初始化！

Answer 38

发现这个东西已经是在讨论java语法的优化，算法还是john_sheep的，参考sagezk2我又小改了下，完全是小动作。
public static int[] sort_scf37_2(int[] nums) {
final int max = nums.length;
int i=0,j=0,k=0,p=0;
int[] temp = new int[max];
for (; i < max; i++) {
temp[nums[i]]++;
}
for (; k < max; ++k) {
for (; j < temp[k]; ++j) {
nums[p++] = k;
}
}
return nums;
}

Answer 39

同意楼上。
1、算法的效率与被排序数据的内在有序性具有密切的关系；
2、算法选定之后就是代码的优化了；       ---- 当然这要看对语言的编译器实现的熟悉程度了。
3、正有搜搜看java.util.random类原代码的念头，可惜没那么多时间。
     不过目前最普遍采用的伪随机数算法基本都是基于线性同余法: Xn = (a * Xn-1 + b) Mod c，只要知道公式中的a、b、c，就~~~~~以上小小，供各位参考吧！

Answer 40

呵呵，我当然知道 N < N*Log N ，我还知道 1 < N呢，那公认最快的是时间复杂度为O(1)了？
呵呵，问题是，有这个算法吗？你说“公认最快的是时间复杂度为O(n)”，那这个算法是什么？排序必定会涉及到数的比较吧？如果要有O(n)的排序算法，那就需要n(1)的比较算法了，有吗？当然，你们可以讨论出来。

Answer 41

public static int[] sort_sweetbai(int[] nums) { // 您的排序代码放在这里啦
int[] copys = new int[nums.length];
for (int i : nums) {
copys[i]=i;
}
return copys;
}

Answer 42

To:r_swordsman 排序必定会涉及到数的比较吧？还真被你说中了，桶排序不需要数字之间的比较。

Answer 43

using System;namespace ConsoleApplication1
{
    class Program
    {
        static int MaxRange = 0;
        static void Main(string[] args)
        {            Test(10 * 10000);
            Console.Read();
            Test(100 * 10000);
            Console.Read();
            Test(1000 * 10000);
            Console.Read();
        }
        public static void Test(int MAX)
        {           
            int[] nums = new int[MAX];
            Random r = new Random(20080623);
            MaxRange = MAX+1;
            for (int i = 0; i < MAX; i++)
            {
                nums[i] = r.Next(MAX);
            }
            long begin = System.DateTime.Now.Ticks;
            Sort(nums);            long end = System.DateTime.Now.Ticks;
            Console.WriteLine("总共" + MAX / 10000 + "万数据，用时" + System.TimeSpan.FromTicks(end - begin).Milliseconds + "毫秒");
            Console.Read();
        }        public static void Sort(int[] a)
        {            int[] p = new int[MaxRange];    
            for (int i = 0; i <a.Length; i++)
            {
               p[a[i]]++;
            }
            for (int i = 0, j = 0; i < MaxRange; i++)
            {
                while (p[i] > 0)
                {
                    a[j++] = i;
                    p[i]--;
                }
            }
             
        }
    }
}

Answer 44

我想问superdullwolf ，你这是桶排序吗，据我知道的好像不是，请教？