Project1

标题: 【纯讨论】优化一下排序算法 [打印本页]

---

作者: 九夜神尊    时间: 2011-7-18 12:37
标题: 【纯讨论】优化一下排序算法
首先要说明一下什么是排序算法。
把一堆数字如
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    时间: 2011-7-18 12:39


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

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

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

---

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

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

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

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

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

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

---

作者: 九夜神尊    时间: 2011-7-18 14:25

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

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

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

---

作者: DeathKing    时间: 2011-7-18 14:26

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

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

---

作者: enghao_lim    时间: 2011-7-18 14:35
新的思路，不适合用在多重复数字与复数，其他未看出。
基本上排序我直接用shell sort了。

---

作者: summer92    时间: 2011-7-18 15:28
- -话说我一直用冒泡排序法

---

作者: 阿龙君    时间: 2011-8-13 14:43
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: summer92    时间: 2011-8-14 21:53

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

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

---

作者: 阿龙君    时间: 2011-8-29 18:09
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: yangff    时间: 2012-1-14 13:35
bogo-sort表示这些算法都是渣渣。。

---

作者: dnf520com    时间: 2012-1-14 23:57
我也是排序法

---

作者: 琪露诺    时间: 2012-1-18 09:53
……貌似如果能直接碰到内存地址排序能快不少0 0

---

作者: dbshy    时间: 2012-1-18 15:38
露珠你的算法是on2的 跟冒泡一个级别的

---

作者: R-零    时间: 2012-1-18 15:47

1. a = [32423,4232342,342423,4,3,234234,23432432,423432,423445,43,4332432,654,65,76572334,34242,4534]
   
2. b = []
   
3. a.size.times{
   
4. m = a.min
   
5. b.push(m)
   
6. a.delete(m)
   
7. }
   
8. a = b
   
9. p a

复制代码

个人认为这样就行了,虽然不懂你说的是什么

---

作者: yangff    时间: 2012-2-4 09:44
stl毫无压力。。std::sort

---

作者: viktor    时间: 2012-2-28 16:22
一般用快排的路过…………
现实中都是*人肉=多路=选择排序……

---

欢迎光临 Project1 (https://rpg.blue/)

Powered by Discuz! X3.1