（升序）思路：比较相邻的元素，如果第一个大于第二个，则交换它们，对每一对执行上一步，从第一对开始到最后一对，当这一步完成时，最大的元素在数组的末尾。重复以上步骤，除了最后一个元素，每次都对越来越少的元素重复以上步骤，直到没有一堆数字可以比较。一次排序：最大的元素在数组的末尾。#单向排序defbubble_Sort(alist):n=len(alist)forjinrange(n-1):#当数组长度为n时，比较的次数为n-1，则成对比较的元素(n1,n2中的n1下标)是从0~n-2ifalist[j]>alist[j+1]:#排序不正确，交换两个位置alist[j],alist[j+1]=alist[j+1],alist[j]returnalistif__name__=="__main__":alist=[54,26,93,17,77,31,44,55,20]print(bubble_Sort(alist))output[26,54,17,77,31,44,55,20,93]每次排序通过后，下一次排序数组需要去掉数组末尾的排序数字defbubble_Sort(alist):n=len(alist)foriinrange(n-1,0,-1):#range(n-1,0,-1)-->n-1,...,1。每进行一次排序，下一次排序的序列长度需要为-1（上一次排序的最大值除外），上一次排序的序列长度为n，第二次为n-1，...,直到最后一个只需要比较两个元素,序列长度为2forjinrange(i):ifalist[j]>alist[j+1]:alist[j],alist[j+1]=alist[j+1],alist[j]returnalistif__name__=="__main__":alist=[54,26,93,17,77,31,44,55,20]print(bubble_Sort(alist))输出[17,20,26,31,44,54,55,77,93]优化：如果给定序列如[17,20,26,31,93,44,55,77]，这样的偏序数组，一次排序后，可以得到一个升序数组。随后的每一次排序都是一种资源的浪费，这种情况应该得到纠正。defbubble_Sort(alist):n=len(alist)foriinrange(n-1,0,-1):count=0#记录每次排序的交换次数，如果count=0，则没有交换，整个数组在range(i)中为j排序：如果alist[j]>alist[j+1]:alist[j],alist[j+1]=alist[j+1],alist[j]count+=1#print(alist)ifcount==0:breakreturnalistif__name__=="__main__":alist=[17,20,26,31,93,44,55,770]print(bubble_Sort(alist))输出[17,20,26,31,44,55,93,770]总结：冒泡排序最好的时间复杂度是O(N)，最差的时间复杂度是O(N^2)平均时间复杂度O(N^2).空间复杂度O(1)可见，冒泡排序的时间复杂度与数组的初始状态有关。
