冒泡排序(Bubble Sort)
一、什么是冒泡排序
冒泡排序是一种简单的排序算法。其基本思想是：两两比较相邻元素的大小，若两元素反序，则交换两元素位置，直至没有反序为止。
假设从小到大排序，两两比较之后，较大的慢慢往后排，较小的数慢慢往前排，最终完成从小到大的排序。这个过程类似于水中冒泡，所以叫冒泡排序。
二、算法的基本描述
假设有n(n>1)个元素需要按从小到大顺序排列，冒泡排序算法如下：
第一次遍历：
1、比较第1个元素与第2个元素的大小，若第1个元素大于第2个元素，则交换两者位置；若第1个元素小于等于第2个元素，则不交换位置；
2、接着比较交换后第2个元素和第3个元素的大小并按结果交换位置；依次比较相邻元素直至第(n-1)个元素和第n个元素完成比较及位置交换，总计比较(n-1)次，将最大值放在序列最末位；
第二次遍历：
将第二大的元素放在倒数第二位；
… …
第(n-1)次遍历：
完成序列从小到大排序
三、算法举例
假设用冒泡排序算法给序列[11,3,36，60,72,38,56]进行排序，其过程如下：
第一次遍历：比较6次(即n-1)，将最大数72放到末尾；
第二次遍历：比较5次(即n-2)，将60放到倒数第二位；
… …
第六次遍历：比较1次(即n-(n-1))，完成序列排序，即：[3,11,36,38,56,60,72]
四、算法时间复杂度从上边举例可以发现，冒泡算法完成排序需要进行的；两两比较的次数总计为：
Sum=(n-1)+(n-2)+(n-3)+… … +2+1=n(n-1)/2=O(n2)
当n较大时，完成冒泡排序所需的两两比较次数就会很大，比较要完成100个数的从小到大排序，则需要计较；完成200个数的比较则需要19900次。因此，冒泡排序算法适合数据元素较少的排序，对于数据元素较多的排序，则会显著增加排序时间。
五、用python实现冒泡排序算法
算法如下：(从小到大排列)
代码中，第二个for循环的范围为range(length-i-1)，这是因为上一次循环已经将length-i-1之前的元素进行过排序了，避免重复无用的循环
运行结果如下：
如果要实现从大到小排序，将代码中第15行的if array[j] > array[j+1]:改为
if array[j]
注：python实现冒泡排序算法原码
”’python实现冒泡排序算法原码”’
”’冒泡排序”’
def bubblesort(array):
length = len(array)
for i in range(length):
for j in range(length-i-1):
if array[j] > array[j+1]:
array[j+1], array[j] = array[j], array[j+1]
return array
list =[11,3,36,60,72,38,56]
list_sorted = bubblesort(list)
print(“冒泡排序结果：”,list_sorted)
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220853.html原文链接：https://javaforall.net
