【竞赛】排序算法的最快实现-继续
由于早上帖子不能访问，我只能忍痛结掉了。并根据现有的成绩分配了积分。
澄清一下这个竞赛的目的，是为了大家共同拿到几个排序的好的算法，注意是几个，而不是一个。
在不同的情况下，各个算法的表现是不同的。
新的测试代码可以自行定义测试的次数和随机的种子。 可以对测试结果自动排序。
下面给出新的测试代码框架。
完整代码太长，需要的请到这里获取， 其中包括已经在另一个帖子给出算法的测试。 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; }}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; }}
[解决办法]
mark!!!
[解决办法]
晕，大意了，没有注意到最大值已经定义了，在这种情况下，肯定是计数的天下，如果没有定义最大值，我还是相信基数是第一的（在整数的情况下）
[解决办法]
int max = nums.length;
[解决办法]
不好意思，态度不太好，向楼主和大家郑重认错，写了代码出来。
核心思路是准备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范围有关，和数据量没关系。
[解决办法]
学习。。这样的帖子才是真正有意义的帖子。顶了。
[解决办法]
看来大家想法都是一样的，都是利用整数与平均分布这两个特性。
俺也想到了，就是动作慢了点。
我稍稍测试了一下：
cpu 的 / * + - 最耗时，
其次是 内存的变量赋值 耗时，
其次是 比较两个整数
然后是 ++ --
再然后是 分配内存
楼上前5名的算法都是一样的，有一个共同的特性：计算非常少，赋值次数很少（2n，无法避免的赋值次数）……
俺是想不到更快的方法了，关注中，说不定有个牛人看懂了random.nextInt();然后又找到了一个很简单的表达式，直接把值一个个赋给原数组了。
[解决办法]
声明：我那个基于n个人的改进算法不参赛，纯属为了精益求精。见 sort_sagezk2。希望还有更快的出现，期待。
另外我所知的改进顺序是：
... -> talent_marquis -> john_sheeping -> SageZk -> scf37 -> SageZk -> ...
如果有遗漏的请楼下回复。
[解决办法]
mark一下
[解决办法]
跟帖。。。。
[解决办法]
小弟不才,没写代码,只测试了代码
(只测试时间是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
当数组中最大元素大于数组长度时,
上述不正确的算法就会数组越界
[解决办法]
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毫秒
[解决办法]
好贴留名，下班再好好学习。。。
[解决办法]
mark................
[解决办法]
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]--;
}
}
}
}
}
[解决办法]
算法局限性太大了！
也就是说针对性太强了！
从数组的生成方式来看，数组中的元素都是非负数且最大元素要小于数组长度
所以有算法要根据数据特征来定了，因此所谓的快速、归并、二分 ...都不在是
最优的了
比赛的这个排序数据规律性，局限性都太强了
之所以那几位排序的速度快，就是因为利用了数据的高度规律性，其实程序利用了这个规律，
根本就不需要机器太多的动作吗，时间当然少了
分析一个算法的思想吧：
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;
}
[解决办法]
MARK 有时间研究一下
[解决办法]
耍点小花招,应该可以更快的.
请楼主再试试.
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; }
[解决办法]
我把桶排序写好了，一般情况下，桶排序应该比计数排序要快，但是我写的桶排序太慢了，
桶排序的思想是把元素按照区间【0，1）划分，然后再每一个区间上进行排序
[解决办法]
这种测试实际意义不大。
如果在实际应用中，首先应充分研究业务数据特点，根据研究结果确定算法。
[解决办法]
非常支持。
只是都在写代码，麻烦你给注释一些，更好的就写个简短的说明。
[解决办法]
数组排序算法已经研究几十年了，公认最快的是时间复杂度为 n*log n，空间复杂度为0的算法，
你们有可能讨论出比这快的吗？
[解决办法]
版主,我的这个代码,试了一下,感觉存在明显的问题,就是显示结果不唯一,或者不准确.能否讨论一下原因?(而且还存在,第一个方法已经排序完成,第二个方法排序已经排好的数组,的问题.)
只给出一个方法,其他代码不变.
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())); // 其它的测试代码将按照顺序逐个放到后面进行测试。 // 某些方法没有使用我提供的标准调用，造成我手工修改，引起不必要的问题。 // 请大家查看我测试的完整代码，并根据你的需求进行完善与修改。 }
[解决办法]
学习
[解决办法]
关于写算法这方面。印度程序员就不错,用最基本的算法 写每个人都能看懂的Code
而不会这么刻意去写高深的代码段，仅仅去完成一个很简单的算法
[解决办法]
靠，我找了半天不知道在哪点收藏。111只好回贴，留做纪念！！
[解决办法]
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; }
[解决办法]
关注一下 ...............
[解决办法]
不错,顶下,又是好东西
[解决办法]
public static int[] sort_sweetbai(int[] nums) { // 您的排序代码放在这里啦 int[] copys = new int[nums.length]; for (int i : nums) { copys[i]=i; } return copys; }
[解决办法]
mark
[解决办法]
学习了
[解决办法]
好久没搞了，真是忘了。看到你们算法，我也有兴趣想想。
------解决方案--------------------
昏 原帖结了啊～
[解决办法]
不知这个帖子是什么意思
难道还有比快速排序和归并排序更快的排序算法么？
[解决办法]