为什么冒泡排序实现永远在循环？

小开

这就是当你使用具有负面含义的变量名时会发生的情况，你需要反转它们的值。以下内容比较容易理解:

sorted = False
while not sorted:
...

另一方面，算法的逻辑有点不对。您需要检查在 for 循环期间是否交换了两个元素。我是这么写的:

def bubble(values):
length = len(values) - 1
sorted = False
while not sorted:
sorted = True
for element in range(0,length):
if values[element] > values[element + 1]:
hold = values[element + 1]
values[element + 1] = values[element]
values[element] = hold
sorted = False
return values

小开

使用 Unsort 变量是错误的; 您希望有一个变量告诉您是否交换了两个元素; 如果已经交换了两个元素，则可以退出循环，否则需要再次进行循环。要解决这里的问题，只需在 if 大小写的正文中放入“ unsort = false”; 删除 else 大小写; 并在 for循环之前放入“ unsort = true”。

小开

你这里有几处错误。第一个是长度，第二个是未排序的使用(如 McWafflestix 所述)。如果要打印列表，您可能还需要返回列表:

mylist = [12, 5, 13, 8, 9, 65]


def bubble(badList):
length = len(badList) - 2
unsorted = True


while unsorted:
for element in range(0,length):
unsorted = False


if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
print badList
unsorted = True


return badList


print bubble(mylist)

你是对的，上面的错误太多了。我的错在于没有通过更多的例子进行测试。

def bubble2(badList):
swapped = True
length = len(badList) - 2


while swapped:
swapped = False
for i in range(0, length):
if badList[i] > badList[i + 1]:


# swap
hold = badList[i + 1]
badList[i + 1] = badList[i]
badList[i] = hold


swapped = True


return badList

小开

Fury 和 Martin Cote 提供的答案修复了无限循环的问题，但是我的代码仍然不能正确工作(对于更大的列表，它不能正确排序).我最终放弃了 unsorted变量，改用计数器。

def bubble(badList):
length = len(badList) - 1
n = 0
while n < len(badList):
for element in range(0,length):
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
n = 0
else:
n += 1
return badList


if __name__ == '__main__':
mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99]
print bubble(mylist)

如果有人能在评论中提供任何关于如何改进我的代码的建议，我将不胜感激。

小开

def bubble_sort(l):
for passes_left in range(len(l)-1, 0, -1):
for index in range(passes_left):
if l[index] < l[index + 1]:
l[index], l[index + 1] = l[index + 1], l[index]
return l

小开

气泡排序的目标是在每轮中移动底部的更重项目，同时向上移动 打火机项目。在内部循环中，比较元素 你不必在每个回合中迭代整个列表。最重的已经排在最后了。交换了变量是一个额外的检查，因此我们可以标记列表现在已经排序，并避免继续进行不必要的计算。

def bubble(badList):
length = len(badList)
for i in range(0,length):
swapped = False
for element in range(0, length-i-1):
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
swapped = True
if not swapped: break


return badList

你的版本1，更正:

def bubble(badList):
length = len(badList) - 1
unsorted = True
while unsorted:
unsorted = False
for element in range(0,length):
#unsorted = False
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
unsorted = True
#print badList
#else:
#unsorted = True


return badList

小开

最佳答案

为了解释为什么您的脚本现在无法工作，我将把变量 unsorted重命名为 sorted。

首先，您的列表尚未排序。当然，我们将 sorted设置为 False。

一旦我们开始 while循环，我们假设列表已经排序。这个想法是这样的: 一旦我们发现两个元素没有在正确的顺序，我们设置 sorted回到 False。sorted将保持 True 只有在没有元素的顺序错误的情况下。

sorted = False  # We haven't started sorting yet


while not sorted:
sorted = True  # Assume the list is now sorted
for element in range(0, length):
if badList[element] > badList[element + 1]:
sorted = False  # We found two elements in the wrong order
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
# We went through the whole list. At this point, if there were no elements
# in the wrong order, sorted is still True. Otherwise, it's false, and the
# while loop executes again.

还有一些小问题有助于提高代码的效率或可读性。

在 for循环中，使用变量 element。从技术上讲，element不是一个元素; 它是一个表示列表索引的数字。而且，它很长。在这些情况下，只需使用一个临时变量名，比如 i表示“ index”。
```
for i in range(0, length):
```
The range command can also take just one argument (named stop). In that case, you get a list of all the integers from 0 to that argument.
```
for i in range(length):
```
The Python Style Guide recommends that variables be named in lowercase with underscores. This is a very minor nitpick for a little script like this; it's more to get you accustomed to what Python code most often resembles.
```
def bubble(bad_list):
```
To swap the values of two variables, write them as a tuple assignment. The right hand side gets evaluated as a tuple (say, (badList[i+1], badList[i]) is (3, 5)) and then gets assigned to the two variables on the left hand side ((badList[i], badList[i+1])).
```
bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]
```

Put it all together, and you get this:

my_list = [12, 5, 13, 8, 9, 65]


def bubble(bad_list):
length = len(bad_list) - 1
sorted = False


while not sorted:
sorted = True
for i in range(length):
if bad_list[i] > bad_list[i+1]:
sorted = False
bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]


bubble(my_list)
print my_list

(顺便说一句，我还删除了你的打印声明。)

小开

# 一个非常简单的函数，可以通过减少第二个数组的问题空间来优化(显然)。但是相同的 O (n ^ 2)复杂度。

def bubble(arr):
l = len(arr)
for a in range(l):
for b in range(l-1):
if (arr[a] < arr[b]):
arr[a], arr[b] = arr[b], arr[a]
return arr

小开

我是一个新鲜的初学者，昨天开始读有关 Python 的书。受到你的例子的启发，我创造了一些可能更加80年代风格的东西，但不管怎样，它还是有点作用的

lista1 = [12, 5, 13, 8, 9, 65]


i=0
while i < len(lista1)-1:
if lista1[i] > lista1[i+1]:
x = lista1[i]
lista1[i] = lista1[i+1]
lista1[i+1] = x
i=0
continue
else:
i+=1


print(lista1)

小开

原始算法的问题在于，如果在列表中进一步使用较低的数字，则不会将其带到正确的排序位置。程序每次都需要回到开始的地方，以确保数字从头到尾排序。

我简化了代码，现在它可以适用于任何数字列表，不管列表是什么，即使有重复的数字。这是密码

mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2]
print mylist


def bubble(badList):
length = len(badList) - 1
element = 0
while element < length:
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
element = 0
print badList
else:
element = element + 1


print bubble(mylist)

小开

def bubble_sort(l):
exchanged = True
iteration = 0
n = len(l)


while(exchanged):
iteration += 1
exchanged = False


# Move the largest element to the end of the list
for i in range(n-1):
if l[i] > l[i+1]:
exchanged = True
l[i], l[i+1] = l[i+1], l[i]
n -= 1   # Largest element already towards the end


print 'Iterations: %s' %(iteration)
return l

小开

def bubbleSort(alist):
if len(alist) <= 1:
return alist
for i in range(0,len(alist)):
print "i is :%d",i
for j in range(0,i):
print "j is:%d",j
print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j])
if alist[i] > alist[j]:
alist[i],alist[j] = alist[j],alist[i]
return alist

Alist = [54,26,93,17,77,31,44,55,20，-23，-34,16,11,11,11]

打印冒泡排序(列表)

小开

def bubble_sort(a):
t = 0
sorted = False # sorted = False because we have not began to sort
while not sorted:
sorted = True # Assume sorted = True first, it will switch only there is any change
for key in range(1,len(a)):
if a[key-1] > a[key]:
sorted = False
t = a[key-1]; a[key-1] = a[key]; a[key] = t;
print a

小开

一个更简单的例子:

a = len(alist)-1
while a > 0:
for b in range(0,a):
#compare with the adjacent element
if alist[b]>=alist[b+1]:
#swap both elements
alist[b], alist[b+1] = alist[b+1], alist[b]
a-=1

这只是将元素从0取到 a (基本上是这一轮中所有未排序的元素) ，并将其与相邻元素进行比较，如果大于相邻元素，则进行交换。最后一轮结束时，对最后一个元素进行排序，然后在没有该元素的情况下再次运行流程，直到所有元素都排序完毕。

不需要条件来判断 sort是否为真。

注意，这个算法只在交换时考虑数字的位置，因此重复的数字不会影响它。

附言。我知道这个问题已经发布很久了，但我只是想分享这个想法。

小开

def bubble_sort(li):
l = len(li)
tmp = None
sorted_l = sorted(li)
while (li != sorted_l):
for ele in range(0,l-1):
if li[ele] > li[ele+1]:
tmp = li[ele+1]
li[ele+1] = li [ele]
li[ele] = tmp
return li

小开

def bubbleSort ( arr ):
swapped = True
length = len ( arr )
j = 0


while swapped:
swapped = False
j += 1
for i in range ( length  - j ):
if arr [ i ] > arr [ i + 1 ]:
# swap
tmp = arr [ i ]
arr [ i ] = arr [ i + 1]
arr [ i + 1 ] = tmp


swapped = True


if __name__ == '__main__':
# test list
a = [ 67, 45, 39, -1, -5, -44 ];


print ( a )
bubbleSort ( a )
print ( a )

小开

Def 冒泡排序(a) : Def 掉期(x，y) : Temp = a [ x ] A [ x ] = a [ y ] A [ y ] = 温度 # 外圈对于范围内的 j (len (a)) : # 切片到中心，内圈，蟒蛇风格对于范围(j，len (a)-j)内的 i: # 查找最小索引和交换如果 a [ i ] < a [ j ] : 交换(j，i) # 找到最大索引然后交换如果 a [ i ] > a [ len (a)-j-1] : 交换(len (a)-j-1，i) 返回

小开

def bubblesort(array):
for i in range(len(array)-1):
for j in range(len(array)-1-i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return(array)


print(bubblesort([3,1,6,2,5,4]))

小开

试试这个

a = int(input("Enter Limit"))




val = []


for z in range(0,a):
b = int(input("Enter Number in List"))
val.append(b)




for y in range(0,len(val)):
for x in range(0,len(val)-1):
if val[x]>val[x+1]:
t = val[x]
val[x] = val[x+1]
val[x+1] = t


print(val)

小开

如果这能帮到你9年后..。它是一个简单的气泡排序程序

    l=[1,6,3,7,5,9,8,2,4,10]


for i in range(1,len(l)):
for j in range (i+1,len(l)):
if l[i]>l[j]:
l[i],l[j]=l[j],l[i]

小开

def merge_bubble(arr):
k = len(arr)
while k>2:
for i in range(0,k-1):
for j in range(0,k-1):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]


return arr
break
else:
if arr[0] > arr[1]:
arr[0],arr[1] = arr[1],arr[0]
return arr

小开

def bubble_sort(l):
for i in range(len(l) -1):
for j in range(len(l)-i-1):
if l[j] > l[j+1]:
l[j],l[j+1] = l[j+1], l[j]
return l

小开

arr = [5,4,3,1,6,8,10,9] # array not sorted


for i in range(len(arr)):
for j in range(i, len(arr)):
if(arr[i] > arr[j]):
arr[i], arr[j] = arr[j], arr[i]


print (arr)

小开

我考虑添加我的解决方案，因为这里的任何解决方案都是具有

更长的时间

更大的空间复杂度

或者做太多手术

那就应该是

所以，我的解决办法是:

def countInversions(arr): count = 0 n = len(arr) for i in range(n): _count = count for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: count += 1 arr[j], arr[j + 1] = arr[j + 1], arr[j] if _count == count: break return count

小开

如果有人对使用列表内涵实现更短的实现感兴趣:

def bubble_sort(lst: list) -> None: [swap_items(lst, i, i+1) for left in range(len(lst)-1, 0, -1) for i in range(left) if lst[i] > lst[i+1]] def swap_items(lst: list, pos1: int, pos2: int) -> None: lst[pos1], lst[pos2] = lst[pos2], lst[pos1]

小开

这里是一个不同的变化的气泡排序没有 for循环。基本上你是考虑的 lastIndex的 array和缓慢的 decrementing它，直到它的第一个索引的数组。

algorithm将继续像这样在数组中移动，直到完成整个传递过程而没有发生任何 swaps。

在性能方面，排序基本上是 Quadratic Time: O(n²)。

class BubbleSort: def __init__(self, arr): self.arr = arr; def bubbleSort(self): count = 0; lastIndex = len(self.arr) - 1; while(count < lastIndex): if(self.arr[count] > self.arr[count + 1]): self.swap(count) count = count + 1; if(count == lastIndex): count = 0; lastIndex = lastIndex - 1; def swap(self, count): temp = self.arr[count]; self.arr[count] = self.arr[count + 1]; self.arr[count + 1] = temp; arr = [9, 1, 5, 3, 8, 2] p1 = BubbleSort(arr) print(p1.bubbleSort())

小开

def bubble_sorted(arr:list): while True: for i in range(0,len(arr)-1): count = 0 if arr[i] > arr[i+1]: count += 1 arr[i], arr[i+1] = arr[i+1], arr[i] if count == 0: break return arr arr = [30,20,80,40,50,10,60,70,90] print(bubble_sorted(arr)) #[20, 30, 40, 50, 10, 60, 70, 80, 90]

小开

def bubblesort(L,s): if s >-1 : bubblesort(L,s-1) for i in range(len(L)-1-s): if L[i]>L[i+1]: temp = L[i+1] L[i+1] = L[i] L[i] = temp return L Nlist = [3,50,7,1,8,11,9,0,-1,5] print(bubblesort(Nlist,len(Nlist)))