前言：
自从毕业了之后就没怎么用到算法，以致于之前学的都忘得差不多了。最近决定抽空再把算法重新学习一下，虽然平时也用不上。
这次学习我是把算法导论、算法技术手册和数据结构(严蔚敏)这三本书混合着看。
正文：冒泡排序的时间复杂度为O(n*n)，它的原理比较简单。基本思路就是从第1个元素开始，依次的把该元素与后一个元素进行比较，如果比后一个元素大则交换它们的位置；每1次全部比较完成之后，最大的那个元素就放在了最后。重复之前的操作，直到所有元素都排好序。
用C语言实现如下：
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
| #include <stdio.h>
void print_list(int *ar, int n)
{
int i;
printf("[ ");
for (i=0; i<n; i++) {
printf("%d ", ar[i]);
}
printf("]\n");
}
void bubble_sort(int *ar, int n)
{
int i, j;
int tmp;
for (i=0; i<n-1; i++) {
for (j=0; j<n-1; j++) {
if (ar[j] > ar[j+1]) {
tmp = ar[j];
ar[j] = ar[j+1];
ar[j+1] = tmp;
}
}
}
}
int main(int argc, char *argv[])
{
int a[] = {5, 3, 16, 2, 10, 14};
int len=sizeof(a)/sizeof(int);
printf("begin: ");
print_list(a, len);
bubble_sort(a, len);
printf("end: ");
print_list(a, len);
return 0;
}
|
冒泡排序演示图片：
