用python实现冒泡算法

有这样一组数列：

［7，6，5，4，3，9，8，2，1］，

我们想排序成这样：

［1，2，3，4，5，6，7，8，9］。

要怎么做呢？第一次，我们可以把9排到最右边。

最终结果就变成这样：

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

然后第二次，再把8拍到倒数第2位，最终结果就变成：

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

以此类推，排列8次以后就完成了。是不是很简单，很像在冒泡啊？

细心的你会发现第一次试除了9的位置有变化，其它数据的位置也都变了。

原始数据 ：

［7，6，5，4，3，9，8，2，1］

第一次排序以后变成 ：

［6，5，4，3，7，8，2，1，9］

而不是1和9换位置如这样：

［7，6，5，4，3，1，8，2，9］

这是为啥呢？因为冒泡算法的第一次的实现过程，为了方便理解暂且称为子过程吧，子过程实际上是这样的：

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

解释：第一次，从第一个数开始和右边的数字比较，如果左边的数比右边的数字大，就左右互换，第一次6和7比较，7大，然后6和7交换位置。

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

解释：第二次，第一个数字比较完后，就接着第二个数字和第三个数字比较，如果左边的数比右边的数字大，就左右互换。

依次类推如下，最终完成了9到最右边：

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

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

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

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

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

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

所以第一遍大循环把9排到最右边实际上是交换了很多次的。逻辑整理清楚了，接下来抽象成编程语言就很简单了。

Python实现方式如下：

到这里是不是就完美了呢？如果觉得是，你就太年轻了。

如果原始数据是［1，2，3，4，5，7，9，8］，其实跑过一次循环就可以达到我们想要的方式，但按上面的代码实现方式，无论如何都都要跑8次大循环，n次子过程。

这样很不科学，所以就有了以下的优化方式，但我们发现子过程，一次都不需要交换的时候，就说明已经排序好了。于是优化的代码如下：

 

到这里是不是就完美了呢？

是的，只能这样了。所以本文结

-------------------------------

注:把最大的往最后面排。

所以 length-i-1 不包括最后面 的数。

 

另外一种写法：

def function1(lists,k):
#   冒泡法
    length = len(lists)
    for i in range(k):
        for j in range(i+1,length):
            if lists[i] > lists[j]:
                lists[j],lists[i] = lists[i],lists[j]

相当于把最小的往最前面排，而不动。

后续循环只看之后的了。