python数组冒泡排序_排序算法（一）冒泡排序

(升序)思路&＃xff1a;

比较相邻元素&＃xff0c;如果第一个比第二个大&＃xff0c;就交换他们

每一对都执行上一步工作&＃xff0c;从开始第一对到末尾最后一对&＃xff0c;这步完成时&＃xff0c;最大的元素位于数组末尾。

重复以上步骤&＃xff0c;除了最后一个元素

每次对越来越少的元素重复以上步骤&＃xff0c;直到没有任何一堆数字需要比较。

一趟排序&＃xff1a;实现最大的元素位于数组末尾。

# 一趟排序

def bubble_Sort(alist):

n &＃61; len(alist)

for j in range(n-1): #数组长度为n,则需比较次数是n-1&＃xff0c;两两比较的元素(n1,n2)中的n1下标是从0~n-2

if alist[j]>alist[j&＃43;1]: #排序不正确&＃xff0c;就交换两者位置

alist[j],alist[j&＃43;1]&＃61;alist[j&＃43;1],alist[j]

return alist

if __name__&＃61;&＃61;"__main__":

alist &＃61; [54,26,93,17,77,31,44,55,20]

print(bubble_Sort(alist))

输出

[26, 54, 17, 77, 31, 44, 55, 20, 93]

每一趟排序结束后&＃xff0c;下一次排序数组需要除开放在数组末尾的已排序数字

def bubble_Sort(alist):

n &＃61; len(alist)

for i in range(n-1,0,-1): # range(n-1,0,-1)--> n-1,...,1. 每执行一趟排序&＃xff0c;下一次排序的序列长度都需要-1(除去上一次排序的最大值),最一趟排序的序列长度为n,第二次为n-1,...,直到最后一趟只需比较两个元素&＃xff0c;序列长度为2

for j in range(i):

if alist[j]>alist[j&＃43;1]:

alist[j],alist[j&＃43;1]&＃61;alist[j&＃43;1],alist[j]

return alist

if __name__&＃61;&＃61;"__main__":

alist &＃61; [54,26,93,17,77,31,44,55,20]

print(bubble_Sort(alist))

输出

[17, 20, 26, 31, 44, 54, 55, 77, 93]

优化&＃xff1a;如果给定的序列如[17, 20, 26, 31,93,44,55,77]&＃xff0c;这样的部分有序数组&＃xff0c;当一趟排序后&＃xff0c;就能得到升序数组。以后的每次排序都是在浪费资源&＃xff0c;对这样的情况进行修正。

def bubble_Sort(alist):

n &＃61; len(alist)

for i in range(n-1,0,-1):

count &＃61; 0 # 记录每一趟排序的交换次数&＃xff0c;如果count&＃61;0&＃xff0c;那就是没有交换&＃xff0c;整个数组已有序

for j in range(i):

if alist[j]>alist[j&＃43;1]:

alist[j],alist[j&＃43;1]&＃61;alist[j&＃43;1],alist[j]

count&＃43;&＃61;1

# print(alist)

if count &＃61;&＃61; 0:

break

return alist

if __name__&＃61;&＃61;"__main__":

alist &＃61;[17, 20, 26, 31,93,44,55,770]

print(bubble_Sort(alist))

输出

[17, 20, 26, 31, 44, 55, 93, 770]

总结&＃xff1a;

冒泡排序最好的时间复杂度是O(N),最坏的时间复杂度是O(N^2)

平均时间复杂度O(N^2).空间复杂度O(1)

可以看出冒泡排序的时间复杂度和数组初始状态有关。