泡沫sorting家庭作业
在课堂上，我们正在做sortingalgorithm，尽pipe我在谈论这些algorithm和编写伪代码的时候很好理解，但是在为它们编写实际的代码时遇到了问题。
这是我在Python中的尝试：
mylist = [12, 5, 13, 8, 9, 65] def bubble(badList): length = len(badList) - 1 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 else: unsorted = True print bubble(mylist) 现在，这个（据我所知）sorting正确，但一旦完成，它只是无限循环。
这个代码是如何被修复的，所以函数能够正确地完成并且正确地分类任何（合理的）大小的列表？
PS我知道我不应该有一个function打印，我应该有一个回报，但我还没有这样做，因为我的代码还没有真正的工作。
为了解释为什么你的脚本不能正常工作，我将重命名unsorted sorted的variables进行sorted 。
起初，你的名单还没有sorting。 当然，我们设置为False 。
只要我们开始while循环，我们假设列表已经sorting。 这个想法是这样的：只要我们发现两个不正确的元素，我们将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不是元素; 这是一个代表列表索引的数字。 而且，这是相当长的。 在这些情况下，只需要使用一个临时variables名称，比如“index”。for i in range(0, length): -
range命令也可以只取一个参数（命名为stop）。 在这种情况下，您将得到从0到该参数的所有整数的列表。for i in range(length): -
Python风格指南build议用小写字母和下划线来命名variables。 对于这样的小剧本来说，这是一个很小的挑剔; 让你习惯Python代码最常见的types更多。
def bubble(bad_list): -
要交换两个variables的值，把它们写成一个元组赋值。 右边被评估为一个元组（例如，
(badList[i+1], badList[i])是(3, 5)），然后被分配到左边的两个variables（(badList[i], badList[i+1])）。bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]
把它放在一起，你得到这个：
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
（顺便说一下，我也删除了您的打印声明。）
泡泡分类的目标是在每一轮中移动较重的物品，同时移动较轻的物品。 在比较元素的内部循环中， 您不必在每一回合中迭代整个列表 。 最重的已经放在最后。 交换的variables是一个额外的检查，所以我们可以标记列performance在sorting，避免不必要的计算。
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
这是当你使用负义的variables名时会发生什么，你需要反转它们的值。 以下将更容易理解：
sorted = False while not sorted: ...
另一方面，该algorithm的逻辑是有点偏离。 你需要检查在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
你使用Unsortedvariables是错误的; 你想有一个variables，告诉你是否交换了两个元素; 如果你这样做了，你可以退出你的循环，否则，你需要再次循环。 要解决你在这里的问题，只要把“unsorted = false”放在你的case里; 删除你的其他情况; 并在for循环之前放入“unsorted = true”。
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
＃一个非常简单的函数，可以通过减less第二个数组的问题空间来优化（显然）。 但是相同的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
那里有几个错误。 第一个是长度，第二个是你使用未分类（如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)
eta：你是对的，上面是鬼鬼祟祟的地狱。 我不好通过一些更多的例子来testing。
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
原始algorithm的问题是，如果列表中的数字越less，它就不会将其带到正确的sorting位置。 程序需要每次都回头，以确保数字一路sorting。
我简化了代码，现在它将适用于任何列表中的数字，不pipe列表是什么，即使有重复的数字。 这是代码
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]
打印bubbleSort（alist）
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的元素（基本上是该轮中所有未sorting的元素），并将其与相邻元素进行比较，如果大于其相邻元素，则进行交换。 在最后一轮，最后一个元素被sorting，并且没有它的过程再次运行，直到所有的元素都被sorting。
不需要sort是否正确的条件。
请注意，该algorithm仅在交换时考虑数字的位置，因此重复的数字不会影响它。
PS。 我知道这个问题已经发布了很长时间，但我只是想分享这个想法。
我是一个新鲜的新手，昨天开始阅读关于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)
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
由愤怒和马丁科特提供的答案解决了无限循环的问题，但我的代码仍然不能正常工作（对于一个更大的列表，它不会正确sorting）。 我最终放弃了unsortedvariables，而是使用了一个计数器。
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)
如果任何人可以提供任何关于如何改善我的代码在评论中的指针，将不胜感激。
