冒泡排序不排序最后一个数字的问题

Question

对编码和算法不熟悉。尝试最简单的一种，气泡排序法。但似乎最后一个数字没有排序?我真的不知道为什么。

原始列表看起来像这样-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)

Answer 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]

Answer 2

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

顺便说一句，最好不要用类型名来调用变量，这里为变量'list'选择另一个名字。

Answer 3

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

我不太懂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()

每次通过对列表中start和hi之间的部分进行排序，hi每通过一次减少一个。

对于额外的学分，如果一个通过没有做任何交换，想办法提前完成。在这种情况下，列表已经按顺序排序了。

Answer 4

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

• 冒泡排序只比较和交换相邻的元素，所以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]