1

编码和算法的新手。尝试最简单的一种，冒泡排序。但似乎最后一个数字没有被排序？实在想不通为什么。

原始列表看起来像这样 -list = [4, 5, 3, 10, 17, 6, 2, 22, 76, 99, 18, 7] 但我的输出看起来像这样 - [99, 2, 3, 4, 5, 6, 7, 10, 17, 18, 22, 76]

由于某种原因，99 没有被交换到后面，我无法确定原因。

list = [4, 5, 3, 10, 17, 6, 2, 22, 76, 99, 18, 7]

def bblSort(list):
    for i in range(len(list)):
        print(list[i])
        for j in range(len(list) - 1):
            if list[i] <list[j+1]:
                list[i], list[j+1] = list[j+1], list[i]

    print(list)
4

4 回答 4

1

冒泡排序可以用两个 for 循环或一个 while 循环和一个 for 循环来实现。这是一个使用 while 和 for 循环的实现，更容易理解。

此函数使用内部 for 循环遍历列表，将每个对象与其后面的对象进行比较，并在必要时交换两者。外部 while 循环确保它在整个列表中一遍又一遍地重复 for 循环，直到不再需要交换为止。

def bubble_sort(unsorted_list):
    my_list = list(unsorted_list) # create a copy to avoid mutating the original list
    unsorted = True
    while unsorted:
        unsorted = False
        for i in range (len(my_list)-1):
            if my_list[i] > my_list[i+1]:
                unsorted = True
                my_list[i] , my_list[i+1] = my_list[i+1], my_list[i]
    return my_list

unsorted_list = [5,2,4,90,140,23,554,32,98,12,15,0,43,-34,10]
print(bubble_sort(unsorted_list))

打印：[-34、0、2、4、5、10、12、15、23、32、43、90、98、140、554]

于 2021-01-29T19:28:14.813 回答
0

您只需要一个循环，因为冒泡排序比较相邻的值。尝试用 i 做一个循环，然后只比较 list[i] 和 list[i+1] （注意列表的末尾）

顺便说一句，最好不要用类型名称调用变量，这里为变量“列表”选择另一个名称。

于 2021-01-29T18:34:50.403 回答
0

对于冒泡排序，您需要多次遍历列表以确保对其进行排序。每次通过都保证将最大的数字移动到正在排序的列表部分的末尾。这意味着您不需要再次对该位置进行排序，因此您只需要在下一次通过时排序到该位置。

我不太了解 Python，所以这是伪代码。它按升序对列表进行就地排序。

bubblesort(list myList)
  for (hi <- myList.length - 1 downto 0) do
    for (lo <- 1 to hi) do
      if (myList[lo - 1] > myList[lo]) then
        swap(myList[lo - 1], myList[lo]) 
      endif
    endfor
  endfor
end bubblesort()

每次通过都会对列表中从开始之间的部分进行排序，并且每次hi通过hi都会减少一个。

如果传球没有做任何交换，想办法提前完成，以获得额外的积分。在这种情况下，列表已经按顺序排序。

于 2021-01-29T19:17:49.630 回答
0

如果您的目标是实现冒泡排序，您的代码有几个问题：

  • lst[j]冒泡排序只比较和交换相邻的元素，所以和之间的比较lst[j+1]。
  • 然后应该相应地调整比较，以lst[j] > lst[j+1]指示这两个值以错误的顺序出现。
  • 虽然不是绝对需要让它工作，但一个好的冒泡排序算法不会验证肯定已经处于正确顺序的对。这意味着内部循环实际上每次i增量都需要少一次迭代，因为列表的末尾将具有已经排序的（增长的）部分。

所以：

def bblSort(lst):
    for i in range(len(lst)):
        for j in range(len(lst) - 1 - i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
于 2021-01-29T19:25:36.850 回答