冒泡排序

基本思想

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

每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；
一旦下趟没有交换，还可提前结束排序

算法实现

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; }
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

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)


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

[32, 34, 45, 54, 56, 90]

  

 

  
1
 

算法分析

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

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/103802745