冒泡排序python优化版本

vlambda
2021-02-23

冒泡排序python优化版本

1.冒泡排序是最基础的排序方式，使用两次for循环完成，内层循环比较两个相邻元素的大小，一次循环完找出最大的元素放在最后，外层循环有多少个待排元素，循环多少遍，这样两层循环完乱序的列表就排序好了，第一次循环8最大，放在最后，第二次6最大放到最后，第三次5最大放到最后，一直到排序完：

代码如下：

def bubble_sort_v1(array): #判断传过来的参数是否为数组 if isinstance(array,list): for i in range(len(array)-1): for j in range(len(array)-i-1): if array[j] > array[j+1]: array[j],array[j+1] = array[j+1],array[j] else: print("参数为数组")
list1 = [234,5,3,23,56,666,888]bubble_sort_v1(list1)print(list1)
结果：[3, 5, 23, 56, 234, 666, 888]

2.上面是最基础版的冒泡排序，这个版本有什么可以优化的地方吗？假如有一种情况是这样大的，只需要把最后两个元素换下位置就排序好了，外层循环一次就排好了，可是以上冒泡排序的代码还是要遍历5次，这样效率就不高了，有什么办法解决这种问题吗？

代码如下：设置一个标志，每次内层循环有元素交换位置，就把flag设置为False,如果内层循环没有交换位置，则证明所有元素都排好序了，跳出大循环

def bubble_sort_v1(array): #判断传过来的参数是否为数组 if isinstance(array,list): for i in range(len(array)-1): flag = True for j in range(len(array)-i-1): if array[j] > array[j+1]: array[j],array[j+1] = array[j+1],array[j] flag = False if flag: break  else: print("参数为数组")
list1 = [234,5,3,23,56,666,888]bubble_sort_v1(list1)print(list1)
结果：[3, 5, 23, 56, 234, 666, 888]

3.还有一种情况，7,8，9,10已经排好序了，只需要把前面排好序就好了，内层循环第3次就把6放到7前面了，但还是要比较7和8,8和9，知道内层循环完，这种情况怎么优化呢？

代码如下：增加两个变量
sort_border：内层循环次数
last_exchange_index：内层最后循环元素交换位置下标
这样把6放到7前面，last_exchange_index = 3,这样每次内层循环数都会减少，解决以上问题

def bubble_sort_v1(array): #判断传过来的参数是否为数组 if isinstance(array,list): #内层循环边界 sort_border = len(array) - 1 #内层最后循环元素交换位置下标 last_exchange_index = 0 for i in range(len(array)-1): flag = True for j in range(sort_border): if array[j] > array[j+1]: array[j],array[j+1] = array[j+1],array[j] flag = False last_exchange_index = j sort_border = last_exchange_index if flag: break
 else: print("参数为数组")
list1 = [234,5,3,23,56,666,888]bubble_sort_v1(list1)print(list1)
结果：[3, 5, 23, 56, 234, 666, 888]