Python 排序方法2：冒泡排序(2)

qiuyouzhi

Python 排序方法2：冒泡排序(2)

对上节的冒泡排序进行改进
上节的冒泡排序有哪些可以优化的点呢？
假设这里有一个列表：

[5, 8, 6, 3, 9, 2, 1, 7]

当排序算法进行到第六轮，第七轮的时候：(标1为有序)
6:             1 1 1 1 1 1
         [1,2,3,5,6,7,8,9]
7:         1 1 1 1 1 1 1
        [1,2,3,5,6,7,8,9]
很明显，在第六轮排序的时候，整个列表已经是有序的了，可是
我们的程序依然继续进行了第七轮排序。
在这种情况下，我们只需要一个变量，用于标记列表的元素是否变换，
如果没有变换，则直接返回这个列表。

代码：

def quick_sort(list1):
    
    for i in range(len(list1) - 1):
        # 默认值为True
        isSorted = True
        for j in range(len(list1) - i - 1):
            if list1[j] > list1[j+1]:
                temp = list1[j]
                list1[j] = list1[j+1]
                list1[j+1] = temp
                #有元素进行交换，所以设它为False
                isSorted = False
        if isSorted:
            break


list1 = [5, 2, 6, 9, 3, 4, 1, 8, 7]
quick_sort(list1)
print(list1)

与第一版相比，这段代码只是多了一个isSorted变量用于标记，
如果元素有变换，则isSorted为False,否则就为True，然后退出循环.

在下一节，我们会继续对冒泡排序进行改进！