python中使用ADT的冒泡排序

6ie5vjzr  于 2023-09-29  发布在  Python
关注(0)|答案(3)|浏览(113)

我有一个任务,输入将是一个列表,我的任务是对列表进行冒泡排序,以升序排列。这是我想要的输入和输出示例。
输入:

45 22 34 79 23

输出量:

22 45 34 79 23
22 34 45 79 23
22 34 45 79 23
22 34 45 23 79
22 34 45 23 79
22 34 45 23 79
22 34 23 45 79
22 34 23 45 79
22 23 34 45 79
22 23 34 45 79

然而,我尝试了一段代码,但它不工作,我试过:

l = list(map(int, input().split()))

swapped = True
while swapped:
    swapped = False
    for i in range(len(l) - 1):
        if l[i] > l[i + 1]:
            l[i] , l[i + 1] = l[i + 1], l[i]
            swapped = True
            print(*l)

我只是想知道Python代码和代码的解释,可以为我提供与赋值中的输出完全相同的结果。

ruoxqz4g

ruoxqz4g1#

算法是正确的,但输出与预期输出不对应,原因有二:
1.您的代码在交换发生时执行print,但我们可以从示例的预期输出中看到,有连续的行是副本,这表明我们需要在 no 交换发生时也进行打印。为此,您必须将print移出if块(取消缩进)
修复后,输出中的行数将比预期的多。这就引出了第二个原因:
1.代码的内部循环总是将数据迭代到len(l) - 1,但这不是必需的。数组的右端将有一个排序的部分,在外部循环的每次迭代中,该部分至少会随着一个元素而增长,因此内部循环不需要迭代该排序的分区。因此,使该循环的迭代次数为动态的:每次从零开始执行循环时将其减1。
例如,通过这些最小的调整,您的代码可以产生预期的输出:

l = list(map(int, inp.split()))

swapped = True
n = len(l) - 1  # number of iterations of the inner loop
while swapped:
    swapped = False
    for i in range(n):
        if l[i] > l[i + 1]:
            l[i] , l[i + 1] = l[i + 1], l[i]
            swapped = True
        print(*l)  # also print when no swap is performed
    n -= 1  # next time the inner loop can make one less iteration

现在,示例输入的输出将是:

22 45 34 79 23
22 34 45 79 23
22 34 45 79 23
22 34 45 23 79
22 34 45 23 79
22 34 45 23 79
22 34 23 45 79
22 34 23 45 79
22 23 34 45 79
22 23 34 45 79
tvmytwxo

tvmytwxo2#

代码来自https://www.programiz.com/dsa/bubble-sort

def bubbleSort(array):
  for i in range(len(array)):
    for j in range(0, len(array) - i - 1):
      if array[j] > array[j + 1]:
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp
      print(*array)
        
        
bubbleSort([45,22,34,79,23])

编辑:该网站有一个算法的解释

wko9yo5t

wko9yo5t3#

下面是修改后的代码:

l = list(map(int, input().split()))

n = len(l)
for i in range(n):
    swapped = False
    for j in range(0, n-i-1):
        if l[j] > l[j+1]:
            l[j], l[j+1] = l[j+1], l[j]
            swapped = True
        print(*l)
    if not swapped:
        break

下面给出了上述代码的解释:
1.读取输入并将数字拆分为列表l。
1.将n定义为列表的长度。这将在外部循环中使用。

  • 对于列表的每个迭代i(从0到n-1),遵循以下步骤:
  • 将交换标志设置为False。这有助于识别当前迭代中是否发生了任何交换。
  • 对于每个元素j(从0到n-i-1),将当前元素与下一个元素进行比较。
  • 如果当前元素l[j]大于下一个元素l[j+1],则交换它们。将swapped标志设置为True,指示已发生交换。打印列表l。
  • 在内部循环完成后,检查swapped是否为False。如果是,这意味着列表已经排序,您可以跳出循环。

相关问题