介绍
冒泡排序(Bubble Sort),是一种计算机科学领域的简单排序算法。它重复的走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把它们交换过来。走访元素的工作是重复的进行,直到没有相邻元素需要交换,也就是说该元素已经排列完成。
举例
给你一串数,让你从小到大排序,则要走n趟,每一趟将最大值“沉底”。
时间复杂度:O(n^2)
e.g.
[5,6,3,1,4,2]
[5,3,1,4,2, 6]
[3,1,4,2, 5,6]
[1,3,2 ,4,5,6]
[1,2, 3,4,5,6]
核心代码
if(a[i] <= a[i + 1]) continue;
else swap(a[i],a[i + 1]);
思路:比较相邻的两个数字,如果前一个数字大,那么就交换两个数字,直到有序。
c++代码
void sort()//从小到大排序
{
for(int i = 0;i < n;i ++)
{
for(int j = 1;j < n - i;j ++)//如果后面的更小,则交换
{
if(nums[j] < nums[j - 1]) swap(a[i],a[i + 1]);
}
}
}
python优化前代码
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
python优化后代码
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
稳定性:稳定
有问题就问,文章有误请联系
有问题就问,文章有误请联系