发表回复 
3种排序算法 插入排序 快速排序 珠排序
2013-12-19, 21 : 35 (这个帖子最后修改于: 2013-12-19 22 : 14 by 兔子.)
3种排序算法 插入排序 快速排序 珠排序
插入排序是我最早实现的,效率最低,具有稳定度.

快速排序是我稍后实现的,查过资料,这种排序法平均速度似乎是最好的.

珠排序非常少见,非常巧妙的实现了排序,并且,速度快得吓人,大概是插入法的25倍,快速法的10倍......网上似乎还没见人贴过算法.


代码: (全选)
#NoEnv

abc:=[82,415,484,494,415,272,170,208,235,7,4,320,140,322,133,467,36,129,234,486,476,37​7,222,230,468,425,136,29,49,218,433,296,428,158,38,153,468,466,180,323,500,207,1​06,260,27,219,73,343,481,357,393,440,77,464,339,3,233,86,228,457,85,294,105,2,58​,145,157,8,208,369,123,93,236,8,486,274,497,46,322,347,43,444,90,234,300,342,471​,211,468,322,52,417,231,329,216,494,399,109,96,476,208,113,90,62,279,284,371,277​,490,0,62,454,406,147,354,21,158,44,67,227,385,230,297,38,375,411,473,107,263,36​6,460,257]

starttime:=A_TickCount
Loop,100
    test:=珠排序(abc)                        ;100次 125
;~ test:=快速排序(abc)                        ;100次 1187
;~ test:=插入排序(abc)                        ;100次 2750
MsgBox,% A_TickCount-starttime
for k,v in test
  s.=v . ","
MsgBox,%s%
return




;大致原理是,从原数组中依次取出旧值,然后根据规则放入新数组中
;规则就是,旧值与新数组中的元素逐个比较,谁大谁排前面
插入排序(数组)
{
  新数组:=[]                        ;创建一个用于保存 "新数组" 的对象
  for k,v in 数组                    ;枚举原始集合中的值
    If (A_Index=1)                    ;将原数组中的第一个元素放入新数组,这样旧的和新的才有的比
        新数组.Insert(v)
    Else
        Loop                        ;下面的过程就是为旧值找到在新数组中的位置
          {
            索引:=新数组.MaxIndex()-A_Index+1        ;从新数组的末尾元素开始比较,比如新数组有 5 个元素,则先从第 5 个开始比.为什么从末尾开始比较?因为末尾总是最小的!
            If (v<=新数组[索引])            ;旧值小于或等于此元素,则放在此元素后面
              {
                新数组.Insert(索引+1,v)
                break
              }
            Else If (索引=1)                ;如果到头了,说明旧值比所有新数组中的元素都大,所以它排第 1
              {
                新数组.Insert(1,v)
                break
              }
          }
  return,新数组
}

;比较难以理解,为何 "返回值" 在 快速排序递归部分() 完成并返回却又没储存它后,依然存在...
;可能是因为它是对象,所以它就有一种全局属性,但是又因为在一个函数中,所以变成了一个在函数中有全局属性的对象吧
;由于无法连接数组,例如 [1,2,3] 插入 [4,5] 后,并不是 [1,2,3,4,5] 而是 [[1,2,3],[4,5]]
;所以必须用一个单独的函数完成返回值的处理
快速排序(数组)
{
  返回值:=[]
  快速排序递归部分(数组,返回值)
  return,返回值
}

;大致原理是通过一个 基准 值,把数组分成比它大的和比它小的两个新数组
;大的放左边,小的放右边
;到大的数组中重复上述过程
;到小的数组中重复上述过程
;这样大的就总是被放在左边,而小的则总是被放在右边
;最后放到只有 1 个值了,于是也就放好了
快速排序递归部分(数组,返回值)
{
  数组元素数量:=数组.MaxIndex()
  If (数组元素数量=1)
    {
      返回值.Insert(数组[1])
      return
    }
  大:=[]
  小:=[]
  基准:=数组[1]                    ;总是以数组第一个值为基准
  Loop
    {
      索引:=A_Index+1                ;索引从 2 开始. 即预留第一个值不参与分区
      If (数组[索引]>=基准)
          大.Insert(数组[索引])
      Else
          小.Insert(数组[索引])
      If (索引=数组元素数量)
          break
    }
  If (大.MaxIndex()="")                ;用预留的第一个值保证两个分区总是都有值. 必须在此处插入,因为此处插入,可以保证插入位置总是在 "小" 的最后面 "大" 的最前面
      大.Insert(基准)
  Else
      小.Insert(基准)
  快速排序递归部分(大,返回值)
  快速排序递归部分(小,返回值)
}

;速度快得惊人...
;只支持正整数,不过负整数稍微改变下,比如取绝对值什么的,也是可以支持的
;原理解释链接 http://www.cnblogs.com/kkun/archive/2011/11/23/2260301.html
;简单说下,不用自己摆珠子,也不用建二维数组,事实上珠子本身就是摆好了的
;需要的就是从第二行开始,逐行模拟珠子下落的过程
;比如有数组 [2,4,1] ,那么元素分别是 2 4 1
;想象它们是竖着放的
;以下文字图在 SCITE 中显示正常
;
;       1                                                       .                                                  .
;       4     -------    再想象它们是一堆珠子    ....    再想象珠子从高处落下来了     ..
;       2                                                       ..                                                 ....
;
;落下来后的结果,就是已经排序好了的结果
珠排序(数组)
{
  Loop,% 数组.MaxIndex()
    {
      当前行:=A_Index+1                        ;因为第 1 行的珠子就是底了,没法跌落了,所以从第 2 行开始模拟珠跌落过程
      Loop
        {
          If (数组[当前行]>数组[当前行-1])            ;如果当前行的珠数目大于下一行,此行就会有珠跌落下去
            {
              temp:=数组[当前行-1]                ;理论上来说,应该是计算有几颗珠跌落到下一行,但我们是逐行模拟跌落过程的,所以其实就是一个珠数目交换的过程
              数组[当前行-1]:=数组[当前行]                                                                      ;比如上面 4 颗,下面 2 颗,跌落下去后,下面必然 4 颗,上面必然 2 颗
              数组[当前行]:=temp

              If (当前行=2)                    ;如果当前就是第 2 行,并且经过 1 次跌落了,显然就不需要再跌落了
                  break
              Else                        ;比如当前是第 5 行,跌落了 1 次,到了第 4 行,显然还需要再次从 4 行跌到 3 行
                  当前行--
            }
          Else                            ;下一行珠数目大于或等于当前行的珠数目,那么珠就无法跌落,所以退出循环,爬高一行再跌
              break
        }
    }
  return,数组
}

忽然想到一点,这些排序算法,包括珠排序,都应该可以支持小数的啊,为什么我看那些资料中说,只支持正整数???
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
[+] 2用户表示感谢兔子
2013-12-20, 10 : 03 (这个帖子最后修改于: 2013-12-20 10 : 07 by 兔子.)
RE: 3种排序算法 插入排序 快速排序 珠排序
好吧 我知道正统的珠排序应该怎么实现了 确实需要建一个二维数组 然后按列移动 而我是按行移动的...

不过如果按列移动 可能存在一个致命问题 就是关联排序比较困难 而我现在的按行移动 则在这方面非常简单.
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
[+] 1用户表示感谢兔子
2013-12-21, 11 : 37
RE: 3种排序算法 插入排序 快速排序 珠排序
赞!你的研究真深入。

AutoHotkey也能完成其他编程语言能做的很多事。
希望它越来越强大,执行效率越来越高!
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
[+] 1用户表示感谢feiyue
2017-09-14, 02 : 37
RE: 3种排序算法 插入排序 快速排序 珠排序
最后一个“珠排序”看懂了,用上了。
建议Loop次数改为“% 数组.MaxIndex() - 1”
因为“当前行:=A_Index+1”,最后会循环到最大行再加1,行不存在值为空。我需要从小到大排列,if的大于改小于“If (数组[当前行]<数组[当前行-1])”,多出来的“空值行”就沉底成了数组里的第一个了,且数组项目增加一个。
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
发表回复 


论坛跳转:


联系我们 | Autohotkey 中文站 | 回到顶部 | 回到正文区 | 精简(归档)模式 | RSS 聚合