Bubble Sort

Theory

关于,冒泡排序的原理及其实现。
关于原理:

有序序列中每一对相邻元素都是顺序的;反之,所有相邻元素均顺序的序列
也必然整体有序。

Code
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>

// 原理: 有序序列中每一对相邻元素都是顺序的;反之,所有相邻元素均顺序的序列
// 也必然整体有序。

using namespace std;

void bubblesort1A( int A[], int n){
bool sorted = false; // 整体排序标志,首先假定尚未进行排序
while(!sorted){ //在尚未确认已经全局排序之前,逐趟进行扫描交换
sorted = true; // 假定已经排序
for (int i =1; i < n; i++ ){
if (A[i - 1] > A[i]){ // 一旦A[i-1]与A[i]逆序,则
swap( A[i-1], A[i]); // 交换之
sorted = false;// 因整体排序不能保证,需要清除排序标志
}
}
n--; // 至此末位元素必然就位, 故可以缩短排序序列的有效长度。
}

}// 借助布尔值标志位sorted, 可以及时提前退出,而不至于总是忙里地做n-1次扫描

// 构造打印数组的函数
void printvector(int a[], int n){
for(int i=0; i < n; i++){
cout << a[i]<< " ";
}
cout << "\n";
}


int main(){
int n=10;
int a[n];
for(int i=0; i<10; i++)
cin>>a[i];
printvector(a, n);
bubblesort1A(a, n);
printvector(a, n);

return 0;
}

关于时间复杂度

参考:TsinghuaX: 30240184.1x Data Structures and Algorithm Design Part I 数据结构与算法设计(上)

击蒙御寇