【纯讨论】优化一下排序算法

九夜神尊

首先要说明一下什么是排序算法。
把一堆数字如
5   6  3   7   9   4  2
这些数字按从小到大的排列成
2  3  4  5  6  7  9

原有的方法我就不说了，懂编程的多少都懂一些。于是我提出一种智能一点的排序方式。

首先 获得 最大值，最小值 2    9

这两个值分别在两个头 ①  ⑦

然后依次遍历剩下的数字。
第一个数  5  
用 （5-2）/（9-2）= 3/7

于是先将5放到3/7的位置上（设法理解 3/7是在 9和2中间，因为2是在0%的位置，9是在100%的位置）

于是排列  2  5  9

第二个数 6
（6-2）/（9-2）= 4/7

于是讲5放到4/7的位置上（因为排列的3个数 于是可以认为2在0% 的位置，5在50%的位置，9在100%的位置所以6应该排在5后面）
检查6是否比50%位置上的数字大，如果小则换位，循环你懂得。
第三个数字3
（3-2）/（9-2）= 1/7
于是排到 33%之前 （因为排了4个数，于是 0%  33%  66%  100%）
2 3 5 9
检查是否比33%位置上的数字大，如果大则换位，循环你懂的。

第四个数字7
（7-2）/（9-2）=5/7 = 71.43%
于是排到 50%之后，75%之前 （因为排列5个数了，0%   25%   50%   75%   100%）
也就是放到3   5之间，
2   3   7   5   9
检查前后大小关系，于是7 和 5换位
2  3  5   7   9

…………
剩下的我就不说了。

其实这就是应用这些数据的大致规律，给一个估计插入位置，就能明显减少不必要的大小对比。

Kimu

先回帖再围观:表示OIer多用快排和二叉树排序

=================================

这个........感觉有点麻烦,编程复杂度MS较高
求源代码(麻烦用C,Pascal,Basic,Ruby中的一个)

DeathKing

第一次找最大值的时候就有一个遍历比较了吧？

那么你在找最大值时的复杂程度就有 θ(n) 吧？而最基本的计数排序在比较理想的情况下就是 θ(n) 。

如果有负数参与进来，这个算法就要改动一下咯：

考虑输入序列： -1， -3， -9， 5， 8， 22，最小值为 -9， 最大值为22

确定 -1 的位置： (-9-(-1)) / ( 22 - (-1)) = -0.3478...

按照理论，-1 是不是应该排在 -9 之前呢？这不就和我们的期望违背了么？

九夜神尊

DeathKing 发表于 2011-7-18 13:34
第一次找最大值的时候就有一个遍历比较了吧？

那么你在找最大值时的复杂程度就有 θ(n) 吧？而最基本的计 ...

这只是一个灵感，大致思路就是猜位置。
我所举的例子就好比让你手动排列这些数字，
你会首先看这个数字大小，然后把这个数字放到大致某个地方。
现在想到哈，其实一开始找最大最小值貌似也不是必须的。
然后还有一个严重的地方就是。
这数字真的可以插进去吗？如果你在第2位插入一个数字，那么后面的数字都会后推一位。
于是……
这只是一个创意。纠结这一个例子当然漏洞百出。

DeathKing

九夜神尊 发表于 2011-7-18 14:25
这只是一个灵感，大致思路就是猜位置。
我所举的例子就好比让你手动排列这些数字，
你会首先看这个数字大 ...

也不说是纠结吧，思路是个好思路，但是最后反应到算法上就要考虑算法的正确性，对不对？

enghao_lim

新的思路，不适合用在多重复数字与复数，其他未看出。
基本上排序我直接用shell sort了。

summer92

- -话说我一直用冒泡排序法

summer92

阿龙君 发表于 2011-8-13 14:43
鄙视LS，超时吧。归并排序现在最好吧，虽然写起来不简单= =不过最优化呢，内存都2G+了
另外我现实排列数字 ...

用了这么久冒泡觉的没区别，真太卡就优化下呗，现在的电脑又不是286，LS乃挖坟啦