0

我正在尝试计算曼哈顿距离的python 8 Puzzle 的不同类型的排序算法。完成气泡并合并。专门尝试实现快速排序。

下面的代码给了我错误：

TypeError: unsupported operand type(s) for +: 'NoneType' and 'list'

队列是具有元素的 8 个拼图状态的节点列表（当前状态、父节点、深度、路径成本、manhattanDistance、MisplacedTilesDistance）

任何改进的指针

def quickSort(queue, length):
    less = []
    pivotList = []
    more = []
    returnList = []
    if length <= 1:
        return queue
    else:
        if queue == []:
            return
        else:    
            pivot = queue[0][3] + queue[0][4]

        for i in queue:

            if i[3]+i[4] < pivot:
                less.append(i)
                print less
                input("yes")
            elif i[3]+i[4] > pivot:
                more.append(i)
            else:
                pivotList.append(i)

        less = quickSort(less, length)
        more = quickSort(more, length)
        #returnList.append(less, pivotList, more)
        return less + pivotList + more
4

2 回答 2

2 
        if queue == []:
            return

你忘了在这里还东西。

于 2013-09-22T09:03:31.680 回答
0

我认为您正在尝试实现 Wikipedia 中的快速排序算法。这是 Python 中的示例实现。您可以根据需要对其进行自定义。

def quickSort(queue):
    lengthOfQueue = len(queue)
    if lengthOfQueue <= 1: return queue
    pivotLocation = lengthOfQueue // 2
    pivot, lesser, greater = queue[pivotLocation], [], []
    for i in range(lengthOfQueue):
        if (i == pivotLocation): continue
        if (queue[i] <= pivot): lesser.append(queue[i])
        else: greater.append(queue[i])
    return quickSort(lesser) + [queue[pivotLocation]] + quickSort(greater)

print quickSort([3, 7, 8, 5, 2, 1, 9, 5, 4])

输出

[1, 2, 3, 4, 5, 5, 7, 8, 9]

解释

伪代码：

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot element 'pivot' from 'array'  // see 'Choice of pivot' below
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), list('pivot'), quicksort('greater')) // two recursive calls

让我们看看程序如何适应这个伪代码。

len(queue)

这用于查找队列的长度。http://docs.python.org/2/library/functions.html#len

如果长度小于或等于 1，我们就按原样返回队列。这意味着，要么队列为空，要么只有一个元素。这是递归的基本条件。

我们选择一个简单的枢轴，即队列的中间元素。所以，我们找到枢轴的位置

pivotLocation = lengthOfQueue // 2

然后我们选择枢轴元素并创建两个空列表，较小和较大。

pivot, lesser, greater = queue[pivotLocation], [], []

现在我们必须创建两个数组，一个将具有小于或等于枢轴的元素，另一个将具有大于枢轴的元素。我们用这个循环来做到这一点。

for i in range(lengthOfQueue):
    if (i == pivotLocation): continue
    if (queue[i] <= pivot): lesser.append(queue[i])
    else: greater.append(queue[i])

我们不想将枢轴元素发送到更小或更大。所以我们像这样跳过枢轴元素。

if (i == pivotLocation): continue

然后我们使用相同的算法对两个数组进行排序，连接结果并返回。

return quickSort(lesser) + [queue[pivotLocation]] + quickSort(greater)
于 2013-09-22T09:15:44.247 回答