数组的三路分区

我想用python实现给定数组的三路分区。数组的三路分区

我的看法：

def partition3(alist, lower, heigher, size): 
    start = 0 
    end = size-1 
    for i in range(size): 
     if alist[i] < lower: 
      alist[i], alist[start] = alist[start], alist[i] 
      start = start+1 
     elif alist[i] > heigher: 
      alist[i], alist[end] = alist[end],alist[i] 
      end = end - 1 
     else: 
      pass 
    return alist 

def sort(alist, low, high): 
    return partition3(alist, low, high, len(alist)) 

print sort([1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32], 10, 20)

预期的结果应该是， 1）所有元素都小于lowRange是第一位的。 2）接下来是范围从低到高的所有元素。 3）所有大于highRange的元素最后出现。

这必须在同一个数组中完成，不应该有三个数组。输入：列表，lowRange和highRange。但我得到，

[1, 5, 4, 2, 14, 20, 32, 54, 87, 98, 3, 1, 20]

需要帮助的，我是缺少在这里的事情。在此先感谢

来源

2017-02-17 Akan

这与排序列表有何不同？你是否期望也有lowRange> highRange？ –

如果你想分区，有3个列表是不是更容易？ – PinkFluffyUnicorn

尝试添加一些打印语句来查看会发生什么。 – PinkFluffyUnicorn

那么你可以做这样的事情（不是最佳的，肯定有一个更好的方法）：

from itertools import chain 
def sort_list_ranges(input_list, low, high): 

    sorted_list = [[] for _ in range(3)] 

    for elem in input_list: 
     if elem < low: 
      sorted_list[0].append(elem) 
     elif elem > high: 
      sorted_list[2].append(elem) 
     else: 
      sorted_list[1].append(elem) 

    print [item for sublist in sorted_list for item in sublist]

它会给你包含值比“低”，中间范围下的列表，并且值高于“高”。

来源

2017-02-17 09:18:29

'sorted_list = [[]，[]，[]]''可以是'sorted_list = [[] for _ in range（3）]' –

确实，这是更pythonic。谢谢！ –

，你必须将列表链接在一起才能使它们变平。 –

下面是根据你的代码的东西：

def partition3(alist, lower, heigher, size): 
    start = 0 
    while alist[start] < lower: 
     start = start + 1 
    end = size-1 
    while alist[end] > heigher: 
     end = end - 1 
    i = start 
    while i <= end: 
     if (i > start) and (alist[i] < lower): 
      alist[i], alist[start] = alist[start], alist[i] 
      while alist[start] < lower: 
       start = start + 1 
     elif alist[i] > heigher: 
      alist[i], alist[end] = alist[end], alist[i] 
      while alist[end] > heigher: 
       end = end - 1 
     else: 
      i += 1 
    return alist 

def sort(alist, low, high): 
    return partition3(alist, low, high, len(alist)) 

print sort([1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32], 10, 20)

它可以在你的榜样，但我不是100％肯定它是正确的。

我想与你原来的版本问题是

如果什么起始点到已较小或终点到已大的元素的元素？那么交换不能解决任何问题，错误顺序可能会生存
如果我跑过去了，该怎么办？它会换回所有正确的上面的第三个元素

来源

2017-02-17 09:36:22

这也适用于你的例子，但可能不是最好的解决方案。

def partition3(alist, lower, heigher, size): 
     start = 0 
     end = size-1 
     i=0 
     while i < size-1: 
      if alist[i] < lower: 
       alist[i], alist[start] = alist[start], alist[i] 
       start = start+1 
       i=i+1 
      elif alist[i] > heigher: 
       if end < i+1: 
        break 
       alist[i], alist[end] = alist[end],alist[i] 
       end = end - 1 
      else: 
       i=i+1 
     return alist 

    def sort(alist, low, high): 
     return partition3(alist, low, high, len(alist)) 

    print sort([1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32], 10, 20)

输出： [1,5，4，2，1，3，14，20，20，98，87，32，54]

感谢@PaulPanzer为端< if语句i + 1必须是第一个

来源

2017-02-17 09:58:09 Lala

尝试'sort（[100，99，0，1]，10，20）';-) –

数组的三路分区

回答

相关问题