常用的排序算法(一)——冒泡排序

前言:

自从毕业了之后就没怎么用到算法,以致于之前学的都忘得差不多了。最近决定抽空再把算法重新学习一下,虽然平时也用不上。
这次学习我是把算法导论算法技术手册数据结构(严蔚敏)这三本书混合着看。


正文:

冒泡排序的时间复杂度为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;
}

冒泡排序演示图片: