數組的三路分區

我想用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）';-) –

數組的三路分區

回答

相關問題