一、冒泡排序简介
冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的列表,每次比较相邻的两项,如果它们的顺序错误就交换它们,直到没有要交换的项为止。冒泡排序算法的时间复杂度为 O(n²)。
二、冒泡排序实现思路
冒泡排序算法的实现思路可以用以下的步骤来描述:
1、比较相邻的元素,如果第一个比第二个大,就交换它们的位置;
2、对每一对相邻的元素都进行步骤1的工作,从开始第一对到结尾最后一对,这样在最后的元素应该会是最大的数;
3、针对所有的元素重复以上的步骤,除了最后一个;
4、持续每次对越来越少的元素重复上述步骤,直到没有任何一对数字需要比较为止。
三、Python实现代码
def bubble_sort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): # Last i elements are already in place for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j]
四、代码解析
1、定义bubble_sort函数,传入一个参数arr,表示待排序的数组;
2、定义变量n,表示数组的长度;
3、通过两个for循环遍历数组,外层循环遍历数组的所有元素,内层循环则遍历数组中前n-i-1个元素,因为最后的n-i-1个元素已经排好序了;
4、当发现arr[j]比arr[j+1]大时,交换这两个元素的位置;
5、最终,得到一个有序的数组。
五、算法优化
冒泡排序算法虽然简单,但是时间复杂度比较高,因此需要对算法进行优化。
1、设置标志位
如果在某次遍历中,没有任何元素被交换,说明数组已经有序,可以停止遍历。
def bubble_sort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): # Last i elements are already in place flag = True for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] flag = False # 如果遍历中没有任何元素被交换,说明数组已经有序,可以停止遍历。 if flag: break
2、优化搜索范围
对于传统的冒泡排序,在每一轮遍历时都要比较整个数组,这样即使数组已经有序,仍然要进行n次遍历。而如果每次遍历时记录最后一次交换的位置,那么后面的元素就已经有序了,可以减少比较次数。
def bubble_sort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): # Last i elements are already in place flag = True # 记录最后一次元素交换的位置 k = n - 1 for j in range(0, k): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # 更新最后一次元素交换的位置 k = j flag = False # 如果遍历中没有任何元素被交换,说明数组已经有序,可以停止遍历。 if flag: break
六、总结
冒泡排序是一种简单有效的排序算法,但是时间复杂度比较高,需要使用优化手段来提高效率。Python实现冒泡排序的代码也比较简单,可以方便地进行调试和优化。