冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们的位置交换过来。走访数列重复地进行直到排序完成。因为越大(小)的元素经过交换会慢慢”浮”到数列的顶端(尾端),就如同碳酸饮料中的气泡一样,故名“冒泡排序”。
算法原理 以从大到小降序排列为例。
第一走轮访开始 —-> 比较相邻的元素- —> 如果第一个元素比第二个元素小,就交换他们的位置,把小的放到后面 —-> 如果第二个比第三个小,同样交换他们的位置,以此类推 —-> 第一轮走访结束
这个时候最小的数就“浮”到最右端了
第二轮走访开始 —-> 比较相邻的元素- —> 如果第一个元素比第二个元素小,就交换他们的位置,把小的放到后面 —-> 如果第二个比第三个小,同样交换他们的位置,以此类推 —-> 第二轮走访结束
这时候倒数第二小的数就“浮”到倒数第二列了
第三轮走访开始 —-> 比较相邻的元素- —> 如果第一个元素比第二个元素小,就交换他们的位置,把小的放到后面 —-> 如果第二个比第三个小,同样交换他们的位置,以此类推 —-> 第三轮走访结束
这时候倒数第三小的数就“浮”到倒数第三列了
所有元素从大到小排序完成
实例演示 对2 3 1 5 4 进行从大到小的降序排列。
第一轮走访开始
2 3 1 5 4 (比较2和3,交换位置)
3 2 1 5 4 (比较2和1,不交换位置)
3 2 1 5 4 (比较1和5,交换位置)
3 2 5 1 4 (比较1和4,交换位置)
3 2 5 4 1 (第一轮走访结束)
最小的数1已经在最后面了,因此第二轮排序只需要对前面四个数进行再比较。
第二轮走访开始
3 2 5 4 1 (比较3和2,不交换位置)
3 2 5 4 1 (比较2和5,交换位置)
3 5 2 4 1 (比较2和4,交换位置)
3 5 4 2 1 (第二轮走访结束)
第二小的数已经排在倒数第二个位置了,所以第三轮只需要比较前两个元素。
第三轮走访开始
3 5 4 2 1 (比较3和5,交换位置)
5 3 4 2 1 (比较3和4,交换位置)
5 4 3 2 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 #include <stdio.h> #define N 10 int main (void ) { int arr[N] = { 0 ,3 ,2 ,5 ,8 ,4 ,7 ,6 ,9 ,1 }; int i = 0 ; int j = 0 ; int temp = 0 ; for (i = 0 ; i < N; i++) { for (j = 0 ; j < N - i; j++) { if (arr[j] < arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; } } } for (i = 0 ; i < N; i++) { printf ("%d " , arr[i]); } return 0 ; }
加入用户输入程序 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 44 45 46 #include <stdio.h> int main (void ) { int arr[1000 ]; int length = 0 ; int i = 0 ; int j = 0 ; int temp = 0 ; printf ("请输入您要排序的数列,数与数之间用空格隔开\n" ); for (i = 0 ; getchar() != '\n' ;i++) { scanf ("%d" , &arr[i]); if (arr[i] >= 0 && arr[i] < 1000 ) { length++; } } printf ("您总共输入了%d个数据,重新排序后的结果如下:\n" ,length); for (i = 0 ; i < length; i++) { for (j = 0 ; j < length - i; j++) { if (arr[j] < arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; } } } for (i = 0 ; i < length; i++) { printf ("%d " , arr[i]); } return 0 ; }
对于上述程序bug的解决方案 如果你认真测试了这个程序,你会发现有bug,程序会吞入用户输入的第一个字符,那么这个bug该如何解决呢。
(我真的整整搞了一下午才发现,这对于刚入门的我也太太太太难了吧,差点就自闭了)
解决方法一:让用户在输入数据之前先输入一个字符给getchar()
解决方案二:申请一个flag整型变量,在第一次获取用户数据时将getchar()短路掉
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 44 int main (void ) { int arr[1000 ]; int length = 0 ; int i = 0 ; int j = 0 ; int temp = 0 ; int flag = 1 ; printf ("请输入您要排序的数列,数与数之间用空格隔开\n" ); for (i = 0 ; flag||getchar() != '\n' ;i++) { if (i == 0 ) flag--; scanf ("%d" , &arr[i]); if (arr[i] >= 0 && arr[i] < 1000 ) { length++; } } printf ("您总共输入了%d个数据,重新排序后的结果如下:\n" ,length); for (i = 0 ; i < length; i++) { for (j = 0 ; j < length - i; j++) { if (arr[j] < arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; } } } for (i = 0 ; i < length; i++) { printf ("%d " , arr[i]); } return 0 ; }
对算法进行封装及调用 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include <stdio.h> int arr[1000 ] ={ 0 } ;int length =0 ;void scanf_sort (int * arr) { int i = 0 ; int flag = 1 ; printf ("请输入您要排序的数列,数与数之间用空格隔开\n" ); for (i = 0 ; flag || getchar() != '\n' ; i++) { if (i == 0 ) flag--; scanf ("%d" , &arr[i]); if (arr[i] >= 0 && arr[i] < 1000 ) { length++; } } printf ("您总共输入了%d个数据,重新排序后的结果如下:\n" , length); } void bubble_sort (int * arr) { int i = 0 ; int j = 0 ; int temp = 0 ; for (i = 0 ; i < length; i++) { for (j = 0 ; j < length - i; j++) { if (arr[j] < arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; } } } } int print_sort (int * arr,int length) { int i = 0 ; for (i = 0 ; i < length; i++) { printf ("%d " , arr[i]); } return 0 ; } int main (void ) { scanf_sort(arr); bubble_sort(arr); print_sort(arr,length); return 0 ; }
运行结果 虽然就实现了简单的**”计算用户输入数据的个数”和 “排序”**的两个功能,但是我真的搞了一天哇,我太菜了……自闭中……
算法优化 以对于3 2 0 1 4 5 6 7 8 9 从大到小排序,经过一轮排序后会变成2 0 1 3 4 5 6 7 8 9
可以发现原序列的后半部分是已经排好顺序了,所以在进行第二轮比较中,2 没必要和4 5 6 7 8 9 再进行多余的比较
用flag代表比较的轮次,k代表该每一轮的比较次数,该优化过程就是在每一轮次中都更新轮次flag的值,不断缩小冒泡排序原始轮次范围N,从而达到排序的最大效率,避免不必要的比较。
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 #include <stdio.h> #define N 10 int main () { int arr[N] = { 3 ,0 ,1 ,2 ,4 ,5 ,6 ,7 ,8 ,9 }; int i = 0 ; int j = 0 ; int k = 0 ; int temp = 0 ; int count = 1 ; int flag = 10 ; while (flag > 0 ) { k = flag; flag = 0 ; for (j = 0 ; j < k - 1 ; j++) if (arr[j] > arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; flag = j + 1 ; } if (flag) count++; } printf ("比较轮次:%d\n" , count); for (i = 0 ; i < N; i++) { printf ("%d " , arr[i]); } printf ("\n" ); return 0 ; }
写在后面 啊啊啊啊啊,终于写完了,裂开了,人没了,写了整整一天,文中的那个bug我搞了整整一下午,这也太虐我这个小白了吧,太难了,还有最后一个算法优化我没有完全敲出来,借鉴其他博主的,改了一点点,还没搞懂代码一步步的逻辑,明日再看。应该还有其他的优化方案吧,后面学算法和数据结构的时候再继续搞。
休息去了…….