经典算法之冒泡排序
冒泡排序
冒泡排序是一种交换的排序方法,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,指到没有反序的记录为止。
大一的时候C语言老师讲过,听的一脸懵,大三重新再来记录记录,加深印象。
既然是交换排序,那谁那谁交换呢?
找了张大佬的图,看的比较清楚
下面以数列{20,40,30,10,60,50}为例,演示它的冒泡排序过程(如下图)。
我们来分析一波数据是如何交换的 - -
我们首先规定排完序的数列左边的数是比较小的,右边数是比较大的。
这是初始位置的数组,令 n = 数组总个数
我们从a[0] 开始两两进行比较大小,即a[0],a[1]比较,a[1],a[2]比较,a[2],a[3]比较,以此类推相互比较
前者比后者大,则交换位置,毕竟越往右数的大小就越大。其中i 表示的是比较几趟,可以判断出来的是比较n -1趟(n是数组个数)
如图,20没有大于40,j就加1,继续比较下一对数a[1],a[2] ...以此类推,等到我们j = n-2时,代表我们走完了一趟。
那么60肯定就是所有数里面最大的一个数了,于是这个数就没必要进行下一趟的比较了,下一趟比较与第一趟类似。
可以看出我们只需要5趟就可以排完这6个数,即趟数 = n-1.
代码附上:
1 #include<stdio.h>
2
3 void BubbleSort(int a[],int len);
4 void swap(int a, int b);
5
6 /*交换函数*/
7 void swap(int *a, int *b){
8 int t = 0;
9 t = *a;
10 *a = *b;
11 *b = t;
12 }
13
14 /*冒泡算法*/
15 void BubbleSort(int a[],int len){
16 int i;
17 for(i = 1; i<len; i++){ //控制比较趟数
18 int j;
19 for(j = len-1; j>=i; j--){ //从另一端开始比较
20 if(a[j] < a[j-1])
21 swap(&a[j],&a[j-1]);
22 }
23 }
24 }
25
26
27 int main(){
28
29 int i;
30 int a[9] = {9,1,5,8,3,7,4,6,2};
31 printf("排序前:");
32 for(i = 0; i < 9; i++)
33 printf("%d ",a[i]);
34
35 printf("\n");
36
37 BubbleSort(a,9);
38 printf("排序后:");
39
40 for(i = 0; i < 9; i++)
41 printf("%d ",a[i]);
42
43 printf("\n");
44 return 0;
45 }
待我们写完一个算法后,要再想想这样的算法是否可以再次优化,可以从时间和空间的方向进行思考。
答案肯定的。我们举出一个例子,如果我们要对待排序序列{2,1,3,4,5,6,7,8,9},自己可以手动模拟一遍,发现只要将2和1互换后,这个序列就已经是排好的了。
一趟就可以拍好的序列,然而我们写的算法,还是要经过9-1趟判断和比较,很明显是降低了程序的性能,降低了程序的效率,做了很多的无用功。
于是我们可以将算法进行优化:
1 /*冒泡算法*/
2 void BubbleSort(int a[],int len){
3 int i;
4 int flag = true; //循环退出标志位
5 for(i = 1; i<len && flag == true; i++){ //控制比较趟数
6 int j;
7 flag = false //如果没有数据交换,这个标志将使退出外层循环,减少了不必要判断
8 for(j = len-1; j>=i; j--){ //从另一端开始比较
9 if(a[j] < a[j-1]){
10
11 swap(&a[j],&a[j-1]);
12 flag = true; //有数据交换的时候flag = false
13 }
14 }
15 }
16 }
冒泡排序的复杂度和稳定性分析
复杂度:
当最好的情况下,也就是要排序的表本身就是有序的,那么我们比较的次数,根据我们最后优化的代码,可以推断出比较了 n-1 趟,没有数的交换,时间复杂度为O(n)
当最坏的情况下,即要排序的数本身是逆序的,此时要比较 ,幷做等量级的记录移动,因此总的时间复杂度为O(n^2).
稳定性:冒泡排序是稳定的排序,它满足稳定的定义。即当两个数相等时不会进行数据交换,所以这个算法是稳定的。
参考文献:
《大话数据结构》
抠了大佬的一张图:https://www.cnblogs.com/skywang12345/p/3596232.html