什么是对列表进行排序的最有效方法，[0,0,1,0,1,1,0]其元素仅为0& 1，而不使用任何内置sort()或sorted()或count()函数。O(n) 或小于
问问题
1436 次
10 回答
11
>>> lst = [0,0,1,0,1,1,0]
>>> l, s = len(lst), sum(lst)
>>> result = [0] * (l - s) + [1] * s
>>> result
[0, 0, 0, 0, 1, 1, 1]
于 2012-06-24T07:21:47.800 回答
4
可以使用许多不同的通用排序算法。但是，在这种情况下，最重要的考虑是所有要排序的元素都属于集合 (0,1)。
正如其他贡献者所回答的那样，有一个简单的实现。
def radix_sort(a):
slist = [[],[]]
for elem in a:
slist[elem].append(elem)
return slist[0] + slist[1]
print radix_sort([0,0,1,0,1,1,0])
必须注意，这是基数排序的一种特殊实现。如果要排序的列表的元素属于定义的有限集合，这可以很容易地扩展。
def radix_sort(a, elems):
slist = {}
for elem in elems:
slist[elem] = []
for elem in a:
slist[elem].append(elem)
nslist = []
for elem in elems:
nslist += slist[elem]
return nslist
print radix_sort([2,0,0,1,3,0,1,1,0],[0,1,2,3])
没有sort()或sorted()或count()功能。在）
于 2012-06-24T07:36:47.973 回答
2
这个是O(n)（你不能少）：
old = [0,0,1,0,1,1,0]
zeroes = old.count(0) #you gotta count them somehow!
new = [0]*zeroes + [1]*(len(old) - zeroes)
由于没有 Python 循环，这可能是您在纯 Python 中获得的更快...
于 2012-06-24T07:21:56.660 回答
1
def sort_arr_with_zero_one():
main_list = [0,0,1,0,1,1,0]
zero_list = []
one_list = []
for i in main_list:
if i:
one_list.append(i)
else:
zero_list.append(i)
return zero_list + one_list
于 2012-06-24T07:26:50.210 回答
0
您只有两个值，因此您提前知道输出的精确结构：它将分为两个不同长度的区域。
于 2012-06-24T07:16:47.520 回答
0
我会试试这个：
b = [0,0,1,0,1,1,0]
def odd_sort(a):
zeroes = a.count(0)
return [0 for i in xrange(zeroes)] + [1 for i in xrange(len(a) - zeroes)]
于 2012-06-24T07:22:21.300 回答
0
您可以使用两个指针遍历列表，一个从开始（i）开始，一个从结束（j）开始，并逐一比较值并在必要时交换它们：
def sort_binary_values(l):
i, j = 0, len(l)-1
while i < j:
# skip 0 values from the begin
while i < j and l[i] == 0:
i = i+1
if i >= j: break
# skip 1 values from the end
while i < j and l[j] == 1:
j = j-1
if i >= j: break
# since all in sequence values have been skipped and i and j did not reach each other
# we encountered a pair that is out of order and needs to be swapped
l[i], l[j] = l[j], l[i]
j = j-1
i = i+1
return l
于 2012-06-24T07:25:17.473 回答
0
我喜欢 JBernado 的答案，但会抛出另一个可怕的选项（尽管我没有对其进行任何分析 - 它不是特别可扩展，因为它依赖于字典哈希的顺序，但适用于 0 和 1）：
from itertools import chain, repeat
from collections import Counter
list(chain.from_iterable(map(repeat, *zip(*Counter(bits).items()))))
或者 - 稍微不那么复杂......
from itertools import repeat, chain, islice, ifilter
from operator import not_
list(islice(chain(ifilter(not_, bits), repeat(1)), len(bits)))
这应该使一切都保持在 C 级别 - 所以它应该是相当优化的。
于 2012-06-24T10:26:14.410 回答
0
您只需要知道原始序列有多长以及其中有多少。
old = [0,0,1,0,1,1,0]
ones = sum(1 for b in old if b)
new = [0]*(len(old)-ones) + [1]*ones
于 2012-06-24T10:33:57.347 回答
0
这是 O(n) 时间和 O(2) 空间的 Python 解决方案。
绝对不需要创建新列表和最佳时间表现
def sort01(arr):
i = 0
j = len(arr)-1
while i < j:
while arr[i] == 0:
i += 1
while arr[j] == 1:
j -= 1
if i<j:
arr[i] = 0
arr[j] = 1
return arr
于 2021-05-19T10:43:45.317 回答