个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
25
4
<分区>
我只是想到了一个有趣的排序方式。我敢肯定有人以前想过它，但我从未见过。它分为两个步骤:
1- 遍历输入列表，将有序(不一定连续)的项目序列拉出到箱中。为每一遍创建一个 bin，直到列表为空。
2- 使用标准合并(重复选择最低的第一个元素)将已排序的 bin 合并回一起
这是我用 Python 制作的原型(prototype)。下面的输出可能更具启发性。
items = len(unsorted)
sortedBins = []
# Pull out bins of sorted numbers, until the unsorted list is depleted:
while( len(unsorted) > 0 ):
print "Unsorted list: " + `unsorted`
highest = float("-inf")
newBin = []
i = 0
while( i < len(unsorted) ):
# Find items in unsorted list that are in order, pop them out:
if( unsorted[i] >= highest ):
highest = unsorted[i]
newBin.append( unsorted.pop(i) )
i=i+1
sortedBins.append(newBin)
print "bin[%i]: "%(len(sortedBins)-1) + `newBin`
print
# Merge all of the sorted bins together:
sorted = []
while( len(sorted) < items ):
lowBin = 0
for j in range( 0, len(sortedBins) ):
if( sortedBins[j][0] < sortedBins[lowBin][0] ):
lowBin = j
print "lowBin: %i: %i" % (lowBin, sortedBins[lowBin][0])
sorted.append( sortedBins[lowBin].pop(0) )
if( len(sortedBins[lowBin]) == 0 ):
del sortedBins[lowBin]
print "sorted:" + `sorted`
如果我不疯狂的话，最坏的情况(一个完全颠倒的列表)似乎需要 n(n+1) 时间(也就是说，n(n+1)/2每个循环)。最好的情况(一个已经排序的列表)将花费 2*n 时间。
编辑:它现在运行了，所以不要再提示了。这是输出，它进一步演示了它是如何工作的:
Unsorted list: [1, 4, 3, 8, 3, 7, 9, 4, 8, 9, 3]
bin[0]: [1, 3, 3, 9, 9]
Unsorted list: [4, 8, 7, 4, 8, 3]
bin[1]: [4, 7, 8]
Unsorted list: [8, 4, 3]
bin[2]: [8]
Unsorted list: [4, 3]
bin[3]: [4]
Unsorted list: [3]
bin[4]: [3]
lowBin: 0: 1
lowBin: 0: 3
lowBin: 0: 3
lowBin: 4: 3
lowBin: 1: 4
lowBin: 3: 4
lowBin: 1: 7
lowBin: 1: 8
lowBin: 1: 8
lowBin: 0: 9
lowBin: 0: 9
sorted:[1, 3, 3, 3, 4, 4, 7, 8, 8, 9, 9]
0
我有几个长度不等的 vector ，我想对其进行cbind。我将 vector 放入列表中，并尝试结合使用do.call(cbind, ...): nm <- list(1:8, 3:8, 1:5)
合并(合并)两个 JSONObjects 的最佳方式是什么？ JSONObject o1 = { "one": "1", "two": "2", "three": "3" }
我在一个表中有许多空间实体，其中有一个名为 Boundaries 的 geometry 字段。我想生成一个具有简化形状/几何图形的 GeoJson 文件。 这是我的第一次尝试: var entitie
谁能说出为什么这个选择返回 3.0 而不是 3.5: SELECT coalesce(1.0*(7/2),0) as foo 这个返回 3: SELECT coalesce(7/2,0) as foo
首先抱歉，也许这个问题已经提出，但我找不到任何可以帮助我的东西，可能是因为我对 XSLT 缺乏了解。 我有以下 XML: 0 OK
有时用户会使用 Windows 资源管理器复制文件并在他们应该执行 svn 存储库级别的复制或合并时提交它们。因此，SVN 没有正确跟踪这些变化。一旦我发现这一点，损坏显然已经完成，并且可能已经对相关
我想组合/堆叠 2 个不同列的值并获得唯一值。 如果范围相邻，则可以正常工作。例如: =UNIQUE(FILTERXML(""&SUBSTITUTE(TEXTJOIN(",",TRUE,TRANSPO
使用iTextSharp，如何将多个PDF合并为一个PDF，而又不丢失每个PDF中的“表单字段”及其属性？ (我希望有一个使用来自数据库的流的示例，但文件系统也可以) 我发现this code可以正常
是否有一个合并函数可以优先考虑公共(public)变量中的非缺失值？ 考虑以下示例。 首先，我们生成两个 data.frames，它们具有相同的 ID，但在特定变量上有互补的缺失值: set.seed
我们正在尝试实现 ALM Rangers 在最新的 Visual Studio TFS Branching and Merging Guide 中描述的“基本双分支计划”。 .从指导: The bas
我在不同目录(3个不同名称)中有很多(3个只是一个例子)文本文件，如下所示: 目录:A，文件名:run.txt 格式:txt制表符分隔 ; file one 10 0.2 0.5 0.
我有一张包含学生等级关系的表： Student Grade StartDate EndDate 1 1 09/01/2009 NULL 2
我在学习 https://www.doctrine-project.org/projects/doctrine-orm/en/2.6/reference/working-with-associatio
我觉得我有世界上最简单的 SVN 用例: 我有一个文件，Test.java在 trunk SVN的。 我分行trunk至 dev-branch . 我搬家Test.java进入 com/mycompa
我有两个数据框，其中一些列名称相同，而另一些列名称不同。数据框看起来像这样: df1 ID hello world hockey soccer 1 1 NA NA
Elasticsearch 中是否缺少以扁平化形式(多个子/子aggs)返回结果的方法？ 例如，当前我正在尝试获取所有产品类型及其状态(在线/离线)。 这就是我最终得到的: aggs [ { key:
如何合并如下所示的 map : Map1 = Map(1 -> Class1(1), 2 -> Class1(2)) Map2 = Map(2 -> Class2(1), 3 -> Class2(2)
我试图通过从netezza服务器导入数据来合并两个数据集。 以下是数据集，其数字为，ID为，字母为，名称为: 下表都是使用命令从netezza导入的: sqoop import --connect n
我有两个数组 $array1 = array('first', 'second', 'third', 'fourth'); $array2 = array('first', 'third', 'fou
我正在 SQL Server 中运行合并。在我的更新中，我只想在值发生更改时更新该行。有一个版本行在每次更新时都会递增。下面是一个例子: MERGE Employee as tgt USING (SE
我是一名优秀的程序员,十分优秀！