Python冒泡排序

Question

嘿，代码运行得很好，非常感谢！

我还有一个问题。我想在这两个字母之间显示一个箭头。我创建了这段代码，但我真的不知道如何让它在被切换的列之间移动。有什么建议吗？

def arrow(lst, i):                 # function for the arrow
if (lst[i], lst[i+1] == lst[i+1], lst[i]):
    t.home()
    t.penup()
                     # im thinking something goes here but i dont know what :P
    t.pendown()
    t.pencolor("red")
    t.right(90)
    t.forward(20)

任何帮助都将不胜感激！谢谢!顺便说一句，剩下的代码就像伊姆兰的代码！:)谢谢yoU！

Answer 1

您的代码看起来很像冒泡排序here的一个版本。你的版本不能工作的主要问题是因为你将索引i处的lst与i-1进行了比较，当i=0时，i-1失败。将该部分更改为：

        if (lst[i] < lst[i + 1]):
            swapped = False
            lst[i+1], lst[i] = lst[i], lst[i+1]

此外，不要在函数外部定义n(理想情况下应该称为bubble_sort或类似的名称)，这是糟糕的编程，是等待发生的bug。我不知道你想用lst = [lst]做什么。可能需要使用不同的变量名。

编辑：我对你的代码做了一些自由的修改。我把所有的绘图调用都放在冒泡排序中。冒泡排序还在内部将列表转换为元组列表，其中元组的第二个元素是颜色。代码末尾的for循环不会做任何有价值的事情。我认为您的主要问题是没有在while循环的每次迭代之间暂停，所以您不会看到列表的元素冒泡。

#!/usr/bin/python
import turtle as t

def draw(lst, width):
  for x in lst:
    height = x[0]
    t.color(x[1])
    t.forward(width)
    t.left(90)
    t.forward(height)
    t.left(90)
    t.forward(width)
    t.left(90)
    t.forward(height)
    t.left(90)
    t.penup()
    t.forward(30)
    t.pendown()

def bubble_sort(orig_lst):  
  lst = [ (x, "blue") for x in orig_lst ]
  n = len(lst)-1 
  t.pensize(3)
  draw(lst, width)
  swapped = True  
  while swapped:  
    swapped = False  
    for i in range(n):  
        if lst[i+1][0] < lst[i][0]:  
            lst[i], lst[i+1] = lst[i+1], lst[i]
            lst[i] = (lst[i][0], "green")  
            swapped = True 
            next = raw_input("hit any key to continue ")
            t.home()
            t.clear() 
            draw(lst,width)
  newLst = [ x[0] for x in lst ]
  return newLst

# TOP LEVEL
original_lst = input("Enter list to be sorted: ")
width = input("Provide the width: ")

newLst = bubble_sort(original_lst)
print "Done! Sorted list is: ", newLst
next = raw_input("hit any key to exit ")

Answer 2

我根据你的代码写了一个冒泡排序：

import types

def bubble_sort(lst):
    assert(type(lst)==types.ListType)
    for index in range(1,len(lst)):
        while index > 0 and lst[index-1] > lst[index]:
            lst[index-1] , lst[index] = lst[index] , lst[index-1]
            index -= 1
    return

lst = input("Enter list to be sorted: ")
print "Original: ",lst
bubble_sort(lst)
print "Sorted: ",lst

测试看起来是这样的：

C:\Users\NAME\Desktop>bubble.py
Enter list to be sorted: [4, 24, 25, 2, 6, -1, 73, 1]
Original:  [4, 24, 25, 2, 6, -1, 73, 1]
Sorted:  [-1, 1, 2, 4, 6, 24, 25, 73]

希望它能帮上忙！

Answer 3

从你的原始代码中只有几个东西需要编辑，最好有两个for循环来检查它的值。同样在此之前，您还使用了[i-1]，它违背了冒泡排序的目的，因为您是从左到右排序的，如果这有意义的话。不管怎样，这就是我所做的。

def swap(lst):
    for i in range (len(lst)):
        for j in range (len(lst)-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                print (lst)


lst = input("Enter list to be sorted: ")
print (lst)
swap(lst)