1

我有一个 100 元素的整数数组。假设它对array 使用这个定义：

: array ( n "name" -- )
     create cells allot
     does> ( index -- addr ) swap cells + ;
100 array atod             \ Make an array with 100 cells
3 atod                     \ Return address of fourth element

现在假设这个atod数组已经填充了从 ATOD 输入读取的 100 个整数值。在处理它之前，我想使用相同的atod数组按值对整数进行永久排序。也就是说，我不关心原始顺序，我只关心它们是否已排序，而且我的内存很薄，所以我不想定义任何其他变量或数组。

你怎么排序？

编辑：根据@Julian Fondren 修复了数组定义。

4

1 回答 1

3

您对 ARRAY 的定义是错误的：

does> cells + ;

在 DOES> 处，数组的地址位于堆栈顶部，而索引（例如 3in 3 atod）位于其下方。所以你的 CELLS 对地址进行操作，这是一个非常没有意义的操作，然后将结果添加到3. 按照惯例，地址在 DOES> 堆栈图片中被忽略，因为堆栈图片是为单词的用户准备的。但是地址在那里。

正确地，

: array ( n "name" -- )
  create  cells allot
  does> ( index -- addr ) swap cells + ;

你对它进行排序就像你对任何东西进行排序一样。确实，有很多关于排序操作的文献，而且都适用于 Forth。所以快速排序、插入排序、bogosort等等，你都可以在 Forth 中完成。

列出了一大堆排序示例

http://rosettacode.org/wiki/Category:Forth

快速排序是一种破坏性（您不关心原始顺序）就地（您不想分配一堆额外的内存）排序，符合您的标准。Rosetta Code在这里有一个 Forth 实现：

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Forth

（该代码延迟 LESSTHAN，就像其他语言中的快速排序实现通常所做的那样，但是 Forth 代码有更多地方可以假设其他语言通常具有的数据类型，因此延迟 LESSTHAN 不足以进行通用排序。）

于 2014-06-09T05:07:40.093 回答