冒泡排序

算法分析

• 目标：从小到大排序
• 循环 n * n 次
• 每次都从数组的第一个数开始比较，每次比较一位
• 每遇到比自己小的值，就替换两者位置
• 每轮后就得到一个最大数
  时间复杂度计算：
  当我们遍历第1遍时，比较了n-1次，把最大的数排在了x[n-1]的位置；
  第2遍比较了n-2次，把第二大的数排在了x[n-2]的位置；
  ...
  第n-1遍比较了1次，把倒数第二大的数排在了x[1]的位置
  这样，我们总共比较的次数是1+2+3+...+(n-1)= n(n-1)/2

代码实现

def bubbleSort(tempArr):
    if len(tempArr) < 2:
        return tempArr
    else:
        for i in range(len (tempArr)):
            for j in range (len(tempArr) - i - 1):
                if tempArr[j] > tempArr[j + 1]:
                    tempArr[j],tempArr[j+1] = tempArr[j+1],tempArr[j]
        return tempArr

if __name__ == '__main__':
    print bubbleSort ([3,2,5,7,6,18,2])