C语言冒泡排序算法及代码

感谢 @向阳_只为一束光 在留言板中指出文章错误。

冒泡排序是排序算法的一种，思路清晰，代码简洁，常被用在大学生计算机课程中。

“冒泡”这个名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

这里以从小到大排序为例进行讲解。

基本思想及举例说明

冒泡排序的基本思想就是不断比较相邻的两个数，让较大的元素不断地往后移。经过一轮比较，就选出最大的数；经过第2轮比较，就选出次大的数，以此类推。

下面以对 3  2  4  1 进行冒泡排序说明。

第一轮 排序过程
3  2  4  1    （最初）
2  3  4  2    （比较3和2，交换）
2  3  4  1    （比较3和4，不交换）
2  3  1  4    （比较4和1，交换）
第一轮结束，最大的数4已经在最后面，因此第二轮排序只需要对前面三个数进行再比较。

第二轮 排序过程
2  3  1  4 （第一轮排序结果）
2  3  1  4 （比较2和3，不交换）
2  1  3  4 （比较3和1，交换
第二轮结束，第二大的数已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。

第三轮 排序过程
2  1  3  4  （第二轮排序结果）
1  2  3  4  （比较2和1，交换）
至此，排序结束。

算法总结及实现

对于具有N个元素的数组R[n]，进行最多N-1轮比较；

第一轮，逐个比较（R[1], R[2]）,  （R[2], R[3]）,  （R[3], R[4]）,  …….  （R[N-1], R[N]） ;  最大的元素会被移动到R[N]上。

第二轮，逐个比较（R[1], R[2]）,  （R[2], R[3]）,  （R[3], R[4]）,  …….  （R[N-2], R[N-1]）；第二大元素会被移动到R[N-1]上。

。。。。
以此类推，直到整个数组从小到大排序。

下面给出了冒泡排序的一般实现和优化实现。一般实现是教科书里常见的实现方法，无论数组是否排序好了，都会进行N-1轮比较； 而优化实现，在数组已经排序好的情况下，会提前退出比较，减小了算法的时间复杂度。

复制纯文本复制

1. #include
2. #include
3.  
4. #define N 8
5.  
6. void bubble_sort(int a[],int n);
7.  
8.  
9. //一般实现
10. void bubble_sort(int a[],int n)//n为数组a的元素个数
11. {
12. //一定进行N-1轮比较
13. for(int i=0; i<n-1; i++)
14. {
15. //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
16. for(int j=0; j<n-1-i; j++)
17. {
18. if(a[j] > a[j+1])
19. {
20. int temp = a[j];
21. a[j] = a[j+1];
22. a[j+1]=temp;
23. }
24. }
25. }
26. }
27.  
28. //优化实现
29. void bubble_sort_better(int a[],int n)//n为数组a的元素个数
30. {
31. //最多进行N-1轮比较
32. for(int i=0; i<n-1; i++)
33. {
34. bool isSorted = true;
35. //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
36. for(int j=0; j<n-1-i; j++)
37. {
38. if(a[j] > a[j+1])
39. {
40. isSorted = false;
41. int temp = a[j];
42. a[j] = a[j+1];
43. a[j+1]=temp;
44. }
45. }
46. if(isSorted) break; //如果没有发生交换，说明数组已经排序好了
47. }
48. }
49.  
50.  
51. int main()
52. {
53. int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
54.  
55. bubble_sort(num, N); //或者使用bubble_sort_better(num, N);
56.  
57. for(int i=0; i<N; i++)
58. printf('%d ', num[i]);
59.  
60. printf('\n');
61.  
62.  
63. system('pause');
64. return 0;
65. }

#include#include#define N 8void bubble_sort(int a[],int n);//一般实现void bubble_sort(int a[],int n)//n为数组a的元素个数{ //一定进行N-1轮比较 for(int i=0; i a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } }}//优化实现void bubble_sort_better(int a[],int n)//n为数组a的元素个数{ //最多进行N-1轮比较 for(int i=0; i a[j+1]) { isSorted = false; int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } if(isSorted) break; //如果没有发生交换，说明数组已经排序好了 }}int main(){ int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; bubble_sort(num, N); //或者使用bubble_sort_better(num, N); for(int i=0; i