Python算法之冒泡排序001

这是我学习python后学习的第一个排序算法。

排序需要关注两个维度，一是时间复杂度，二是稳定性。

冒泡排序的时间复杂度为O（n^2）；属于稳定排序算法。

冒泡排序原理：有一个无序数组（A，下标为i,元素个数为n），要对无需数组进行排序。第一轮比较：第一步开始进行相邻两个元素的对比，若第1个位于第2位，交换他们的位置；第二步，用刚才比较大的那个数字和第3位数比较，谁大谁就在第3位。。。以此类推，直至最大的数放在最后一位。第二轮比较：重复第一轮的方法，直至第n-1轮（即len(A[i])-1）轮比较，此时我们便得到了一个有序的数组。

优化方案：从上边的原理可以看出，冒泡排序每轮比较都需要进行n-1次两两比较；但是我们可以知道，每做完一轮比较，最后一个位置的数就已经定下来了，所以，我们可以在后续每轮的比较中，减少一次两两比较。

好啦，准备工作已说完，python源码现身：

# coding:utf-8

# 冒泡排序

defpaopao(A):

    print A

for i in range(len(A)-1,0,-1):    # 外层循环是要比较的次数

    print i

    for j in range(i):    # 内层循环是两两比较,交换

        if A[j] > A[j+1]:

            A[j],A[j+1] = A[j+1],A[j]# python特有的交换两个元素的公式

            # max1 = A[j]

            # A[j] = A[j+1]

            # A[j+1] = max1

        print A

if__name__ =="__main__":

    s = [8,6,7,4,2,3,5]

    # 打印原数组

    print s

    # 打印排序后的数组

    paopao(s)

    print s