基数排序在Lua中不起作用。

2011-10-13 16:9:18
收藏：0
阅读：91
评论：2

首先，我应该提到我编码时间不长，尽管这在我的代码中可能是显而易见的 :P

我遇到了两个问题，第一个是排序没有正确运行，但确实按其长度对数字进行了排序。如果有帮助的话，我会非常感激。

其次，它改变了它抓取的表格和返回的表格（不知道为什么）。如何防止它改变抓取的表格？

我更喜欢如果人们不会发布完全优化的预制代码，因为我不会通过那种方式学习或理解任何东西。 

function radix_sort(x)

   pass, bucket, maxstring = 0, x, 2

   while true do

      pass = pass + 1
      queue = {}

      for n=#bucket,1,-1 do

         key_length = string.len(bucket[n])
         key = bucket[n]

         if pass == 1 and key_length > maxstring then
            maxstring = key_length
         end

         if key_length == pass then
            pool = string.sub(key, 1,1)

            if queue[pool + 1] == nil then
               queue[pool + 1] = {}
            end

            table.insert(queue[pool + 1], key)
            table.remove(bucket, n)
         end
      end

      for k,v in pairs(queue) do
         for n=1,#v do
            table.insert(bucket, v[n])
         end
      end

      if pass == maxstring then
         break
      end
   end

   return bucket
end

原文链接 https://stackoverflow.com/questions/7757063

点赞
stackoverflow用户33252
stackoverflow用户33252 
`pool = string.sub(key, 1,1)` 表示总是查看字符串的第一个字符；也许你想用 `string.sub(key, pass, 1)`。
2011-10-13 16:40:02
stackoverflow用户596285
stackoverflow用户596285 
function radix_sort(x)

   pass, maxstring = 0, 0

   -- 为了避免覆盖 x，将其复制到bucket中，同时还可以初始化 maxstring
   bucket={}
   for n=1,#x,1 do
      --因为我们可以，将所有条目转换为字符串以用于下面的字符串函数
      bucket[n]=tostring(x[n])
      key_length = string.len(bucket[n])
      if key_length > maxstring then
         maxstring = key_length
      end
   end

   -- 当我们可以在这里设置条件时，不喜欢“while true ... break”
   while pass <= maxstring do

      pass = pass + 1

      -- 初始化队列和所有队列条目，这样ipairs就不会跳过下面的任何内容
      queue = {}
      for n=1,10,1 do
         queue[n] = {}
      end

      -- 按顺序处理桶条目，进行LSD基数排序
      for n=1,#bucket,1 do

         key_length = string.len(bucket[n])
         key = bucket[n]

         -- 对于string.sub，从末尾开始（LSD排序），使用-pass
         if key_length >= pass then
            pool = tonumber(string.sub(key, pass*-1, pass*-1))
         else
            pool = 0
         end

         -- 添加到合适的队列，但不需要从桶中删除，下方代码中将重新初始化桶
         table.insert(queue[pool + 1], key)
      end

      -- 清空桶并重置，使用ipairs按顺序调用队列
      bucket={}
      for k,v in ipairs(queue) do
         for n=1,#v do
            table.insert(bucket, v[n])
         end
      end
   end

   return bucket
end

以下是测试运行的结果：

> input={55,2,123,1,42,9999,6,666,999,543,13}
> output=radix_sort(input)
> for k,v in pairs(output) do
>   print (k , " = " , v)
> end
1    =  1
2    =  2
3    =  6
4    =  13
5    =  42
6    =  55
7    =  123
8    =  543
9    =  666
10   =  999
11   =  9999
2011-10-14 02:06:44

作者:

stackoverflow用户993810

stackoverflow用户993810
推荐文章