首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >排序——冒泡排序

排序——冒泡排序

原创
作者头像
ruochen
修改2021-06-30 10:44:38
1.1K0
修改2021-06-30 10:44:38
举报

冒泡排序

基本思想

  • 依次比较相临两个数据元素的大小,若逆序则交换两个数据元素,否则不交换。
  • 当完成一趟交换以后,最大的元素将会出现在数据序列的最后一个位置。
  • 重复以上过程,直到待排序序列中没有逆序为止。

每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;

       **一旦下趟没有交换,还可提前结束排序**

算法实现

c++代码实现

// 原始冒泡排序
void bubblf_sort(SqList &L){
	// 从大到小有序
	for(i = 1; i <= L.length; ++i)
		for(j = 1; j <= L.length - 1; j++){
			if(L.r[j + 1].key < L.r[j].key){
				temp = L.r[j + 1];
				L.r[j + 1] = L.r[j];
				L.r[j] = temp;
			}

		}
}

// 改进后的算法
void bubblf_sort(SqList &L){
	for(i = 1, change = true; i <= L.length - 1 && change; i++){
		change = false;
		for(j = 1; j < L.length - i; ++i)
			if(L.r[j + 1].key < L.r[j].key){
				temp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = temp;
				change = true;
			}
	}
}

python代码实现

'''冒泡排序-BubbleSort'''
def bubble_sort(alist):
	for j in range(len(alist)-1,0,-1):
		# j表示每次遍历需要比较的次数,是逐渐减小的
		for i in range(j):
			if alist[i] > alist[i+1]:
				alist[i], alist[i+1] = alist[i+1], alist[i]

l = [54, 45, 32, 34, 56, 90]
bubble_sort(l)

print(l)
[32, 34, 45, 54, 56, 90]

算法分析

  • 时间复杂度为 O(n^2) - 最好情况下: 只需 1趟排序,比较次数为 n-1,不移动 - 最坏情况下:需 n-1趟排序,第i趟比较n-i次,移动3(n-i)
  • 空间复杂度为 O(1)
  • 是一种稳定的排序方法

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 冒泡排序
    • 基本思想
      • 算法实现
        • 算法分析
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档