问题描述
如图所示，此算法将1000万个中最大的1000数排序消耗时间是2000+ms，有更快的排序算法吗？请附完整代码，谢谢！usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespace快速排序Bata2{usingSystem;publicstaticclassProgram{publicstaticvoidMain(){System.Diagnostics.Stopwatchwatch=newSystem.Diagnostics.Stopwatch();constintz=10000000;//随机生成一千万个数。int[]a=newint[z];Randomrandom=newRandom();for(inti=0;i<z;i++){a[i]=random.Next(0,z);}watch.Start();//计时器开始。QuickSort(a,0,z-1);watch.Stop();//计时器结束。for(inti=z-1000;i<z;i++){Console.WriteLine(a[i]);}stringtime=watch.ElapsedMilliseconds.ToString();Console.Write("排序所用时间:"+""+time+"ms");Console.Write("rn");}privatestaticvoidQuickSort(int[]a,intlow,inthigh){if(low>=high){return;}intpivot=QuickSortOnce(a,low,high);//输出每一次排序。//对枢轴左端进行排序。QuickSort(a,low,pivot-1);//对枢轴右端进行排序。QuickSort(a,pivot+1,high);}privatestaticintQuickSortOnce(int[]a,intlow,inthigh){//将首个元素作为枢轴。intpivot=a[low];inti=low,j=high;while(i<j){//从右往左，寻找首个小于povit的元素。while(a[j]>=pivot&&i<j){j--;}//执行到此，j一定指向从右端起首个小于或等于povit的元素。执行替换。a[i]=a[j];//从左往右，寻找首个大于povit的元素。while(a[i]<=pivot&&i<j){i++;}////执行到此，j一定指向从右端起首个大于或等于povit的元素。执行替换。a[j]=a[i];}//退出while循环，执行至此，必定是i==j的情况。i（或j）指向的既是枢轴的位置，定位该趟排序的枢轴并将该位置返回。a[i]=pivot;returni;}}}
解决方案
本帖最后由 sinat_32928967 于 2015-12-17 16:36:42 编辑
解决方案二：
Array.Sort(a);
解决方案三：
引用1楼shingoscar的回复:
Array.Sort(a);
？能详细解释吗?
解决方案四：
引用2楼sinat_32928967的回复:
Quote: 引用1楼shingoscar的回复:
Array.Sort(a);？能详细解释吗?
.net自带排序函数，替换QuickSort你自己试试，要什么详细解释？
解决方案五：
你自己写一个希尔排序，你会发现比快排快。。。
解决方案六：
你那一堆的Console.WriteLine的时间就够你跑一会儿了一千次打印一个9个字符的字符串就接近两秒了字符串越多越耗时打印一个百度首页的html源码就能让你飞一会儿等个几秒钟。。在我用过的会的算法中就属归并排序最快了。。
解决方案七：
windows下的中断打印效率是很低的同样的代码放到linux上简直是天壤之别。。所以在需要效率的操作中重来不会去执行打印
解决方案八：
最快速的当然是基数排序。开一个10000000的数组，遍历你的数据，将对应下标+1最后按照这个数组输出一次，ok
解决方案九：
我觉得还是使用LinQ来排序比较合适
解决方案十：
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespaceConsoleApplication1{classProgram{staticvoidMain(string[]args){System.Diagnostics.Stopwatchwatch=newSystem.Diagnostics.Stopwatch();constintz=10000000;//随机生成一千万个数。int[]a=newint[z];Randomrandom=newRandom();for(inti=0;i<z;i++){a[i]=random.Next(0,z);}watch.Start();//计时器开始。a.OrderBy(n=>n);watch.Stop();stringtime=watch.ElapsedMilliseconds.ToString();Console.Write("Linq排序所用时间:"+""+time+"ms");Console.Write("rn");for(inti=0;i<z;i++){a[i]=random.Next(0,z);}watch=newSystem.Diagnostics.Stopwatch();watch.Start();Array.Sort(a);watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("Array.Sort排序所用时间:"+""+time+"ms");Console.Write("rn");Console.ReadKey();}}}
Linq排序所用时间:1msArray.Sort排序所用时间:1461ms
解决方案十一：
引用1楼shingoscar的回复:
Array.Sort(a);
1楼正解。对于int型数组的排序算法不需要重写Sort方法。这个直接就能搞定。
解决方案十二：
再不行你也可以a.OrderBy(x=>x).toArray();降序是a.OrderByDistinct(x=>x).toArray();
解决方案十三：
引用9楼hegx2001的回复:
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespaceConsoleApplication1{classProgram{staticvoidMain(string[]args){System.Diagnostics.Stopwatchwatch=newSystem.Diagnostics.Stopwatch();constintz=10000000;//随机生成一千万个数。int[]a=newint[z];Randomrandom=newRandom();for(inti=0;i<z;i++){a[i]=random.Next(0,z);}watch.Start();//计时器开始。a.OrderBy(n=>n);watch.Stop();stringtime=watch.ElapsedMilliseconds.ToString();Console.Write("Linq排序所用时间:"+""+time+"ms");Console.Write("rn");for(inti=0;i<z;i++){a[i]=random.Next(0,z);}watch=newSystem.Diagnostics.Stopwatch();watch.Start();Array.Sort(a);watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("Array.Sort排序所用时间:"+""+time+"ms");Console.Write("rn");Console.ReadKey();}}}Linq排序所用时间:1msArray.Sort排序所用时间:1461ms
你这样计算时间就是有问题的好不，OrderBy只是建了个对象，根本就没排序，要比较应该这样写：watch.Start();vark=a.OrderBy(n=>n);foreach(varitemink){}watch.Stop();
解决方案十四：
random.Next(0,z);
这行代码意味着应该考虑计数排序。
解决方案十五：
试试System.Diagnostics.Stopwatchwatch=newSystem.Diagnostics.Stopwatch();constintz=10000000;//随机生成一千万个数。int[]a,b=newint[z];Randomrandom=newRandom();for(inti=0;i<z;i++){b[i]=random.Next(0,z);}do{Array.Copy(b,a=newint[z],z);watch.Restart();//计时器开始。QuickSort(a,0,z-1);watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}stringtime=watch.ElapsedMilliseconds.ToString();Console.Write("QuickSort排序所用时间:"+""+time+"ms");Console.Write("rn");Array.Copy(b,a=newint[z],z);watch.Restart();//计时器开始。Array.Sort(a);watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("Array.Sort排序所用时间:"+""+time+"ms");Console.Write("rn");Array.Copy(b,a=newint[z],z);watch.Restart();int[]c=newint[z];foreach(intvina)++c[v];intai=0,n=0;foreach(intvinc){for(intj=Math.Min(ai+v,1000);ai!=j;a[ai++]=n);if(ai==1000)break;++n;}//计时器开始。watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("计数排序所用时间:"+""+time+"ms");Console.Write("rn");Array.Copy(b,a=newint[z],z);watch.Restart();//计时器开始。fastCSharp.arrayExtension.sort(a);watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("fastCSharp.arrayExtension.sort排序所用时间:"+""+time+"ms");Console.Write("rn");Array.Copy(b,a=newint[z],z);watch.Restart();//计时器开始。fastCSharp.arrayExtension.rangeSort(a,0,1000);watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("fastCSharp.arrayExtension.rangeSort排序所用时间:"+""+time+"ms");Console.Write("rn");Array.Copy(b,a=newint[z],z);watch.Restart();//计时器开始。a=fastCSharp.algorithm.quickSort.getTop(a,1000).GetArray();//未对外开放watch.Stop();//计时器结束。//for(inti=z-1000;i<z;i++)//{//Console.WriteLine(a[i]);//}time=watch.ElapsedMilliseconds.ToString();Console.Write("fastCSharp_getTop排序所用时间:"+""+time+"ms");Console.Write("rn");Console.Write("rn");Console.ReadKey();}while(true);
QuickSort排序所用时间:1075msArray.Sort排序所用时间:1082ms计数排序所用时间:146msfastCSharp.arrayExtension.sort排序所用时间:161msfastCSharp.arrayExtension.rangeSort排序所用时间:89msfastCSharp_getTop排序所用时间:7msQuickSort排序所用时间:1053msArray.Sort排序所用时间:1068ms计数排序所用时间:145msfastCSharp.arrayExtension.sort排序所用时间:132msfastCSharp.arrayExtension.rangeSort排序所用时间:88msfastCSharp_getTop排序所用时间:6ms
解决方案：
试试这个
解决方案：
修改一下#14最后一个测试的代码a=fastCSharp.algorithm.quickSort.getTop(a,1000).GetArray();
这个仅仅是top1000，并没有对这1000个数排序，应该修改为a=fastCSharp.subArrayExtension.sort(fastCSharp.algorithm.quickSort.getTop(a,1000)).sort().GetArray();
不过测试时间没有差别，1000个数的排序相对与1000W个数的扫描根本不算什么。
解决方案：
已推荐………………
解决方案：
观摩观摩学生
解决方案：
该回复于2016-01-31 23:20:11被版主删除
解决方案：
进来支持了呢
解决方案：
用用多线程？
解决方案：
"此算法将1000万个中最大的1000数排序消耗时间是2000+ms",这个需求不需要将整个数组排序，使用最小堆，速度比这快得多。请参阅《寻找最大的Ｋ个数》http://blog.csdn.net/xiaoding133/article/details/8037086
解决方案：
楼主的代码存在严重的问题，在极端的条件下（对降序的数组做升序排序），程序处于假死状态，不知道什么时候会结束for(inti=0;i<z;i++){a[i]=z-i;}
应写解决好本身的算法，再去下结论
解决方案：
我觉得还是使用LinQ来排序比较合适
解决方案：
测试。。。。。
解决方案：
想起了一个视频挺魔性的...