当前位置:   article > 正文

冒泡排序(超详细图解加代码解析,5分钟看懂)

冒泡排序

 目录

1.冒泡排序的定义

2.冒泡排序的原理

3.代码及其解析

4.冒泡排序的改进

5.实现冒泡排序函数


生命中永远会有令人懊恼的事,但我知道,我们是为了不留遗憾活着的,对吗?

1.冒泡排序的定义

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端,但是在广泛适用后,冒泡排序可以用来排任意顺序。

2.冒泡排序的原理

假设要将已知无需数列按从小到大排列,将第一个元素与后面的元素依次比较,如果必后面的元素小,就与后面某个元素交换位置,然后用这个元素再依次往后比较,遇到比这个元素小的就与这个元素交换,直到最后一个元素,就完成了一趟冒泡排序,则最后一个元素一定是这个序列里最大的一个元素;然后开始第二趟冒泡排序,继续从第一个元素开始往后一次比较,遇到较小的就交换位置,直到倒数第二个数,那么最后倒数第二个数就变成了第二大的数.......依次排完序列中所有的数,那么这个数的顺序就会变成从小到大,下面我用图来演示

第一趟冒泡排序,是对序列中所有数进行操作

第 i 趟冒泡排序,是对序列中除最后一个数外(10-i)个数进行操作

3.代码及其解析

  1. #include<stdio.h>
  2. int main()
  3. {
  4. int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
  5. int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
  6. int i = 0;
  7. printf("排序前的数组:");
  8. for (i = 0; i < sz; i++)
  9. {
  10. printf("%d ", arr[i]);
  11. }
  12. printf("\n");
  13. for (i = 0; i < sz - 1; i++)
  14. {
  15. int j = 0;
  16. for (j = 0; j < sz - 1 - i; j++)
  17. {
  18. if (arr[j] > arr[j + 1])
  19. {
  20. int tmp = arr[j];
  21. arr[j] = arr[j + 1];
  22. arr[j + 1] = tmp;
  23. }
  24. }
  25. }
  26. printf("排序后的数组:");
  27. for (i = 0; i < sz; i++)
  28. {
  29. printf("%d ", arr[i]);
  30. }
  31. printf("\n");
  32. return 0;
  33. }

运行结果:

 代码解析:外部循环控制冒泡排序的趟数,for循环从0开始,循环sz-1(数组元素-1)次,内部循环控制每次具体的冒泡排序过程,因为每趟冒泡排序需要进行比较的次数递减,所以在循环的控制条件那再减去i来控制每趟冒泡排序进行的比较次数。在内部循环的循环体内,对这趟冒泡排序需要排序的元素进行遍历,小的元素放前面,大的逐次往后走,没趟冒泡结束后都能确定一个元素的位置。(sz-1)趟冒泡排序结束后,冒泡排序及就结束了。当然,如果想进行从大到小排序,只需要改变冒泡排序的判断部分,将大的元素放前面,小的元素往后走即可,代码如下:

  1. #include<stdio.h>
  2. int main()
  3. {
  4. int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
  5. int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
  6. int i = 0;
  7. printf("排序前的数组:");
  8. for (i = 0; i < sz; i++)
  9. {
  10. printf("%d ", arr[i]);
  11. }
  12. printf("\n");
  13. for (i = 0; i < sz - 1; i++)
  14. {
  15. int j = 0;
  16. for (j = 0; j < sz - 1 - i; j++)
  17. {
  18. if (arr[j] < arr[j + 1])
  19. {
  20. int tmp = arr[j];
  21. arr[j] = arr[j + 1];
  22. arr[j + 1] = tmp;
  23. }
  24. }
  25. }
  26. printf("排序后的数组:");
  27. for (i = 0; i < sz; i++)
  28. {
  29. printf("%d ", arr[i]);
  30. }
  31. printf("\n");
  32. return 0;
  33. }

运行结果:

4.冒泡排序的改进

由于冒泡排序的时间复杂度实在太高,所以冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。 

  1. #include<stdio.h>
  2. int main()
  3. {
  4. int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
  5. int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
  6. int i = 0;
  7. printf("排序前的数组:");
  8. for (i = 0; i < sz; i++)
  9. {
  10. printf("%d ", arr[i]);
  11. }
  12. printf("\n");
  13. int flag = 0;
  14. for (i = 0; i < sz - 1; i++)
  15. {
  16. int j = 0;
  17. for (j = 0; j < sz - 1 - i; j++)
  18. {
  19. if (arr[j] >arr[j + 1])
  20. {
  21. int tmp = arr[j];
  22. arr[j] = arr[j + 1];
  23. arr[j + 1] = tmp;
  24. flag++;
  25. }
  26. }
  27. if(flag==0)
  28. break;
  29. }
  30. printf("排序后的数组:");
  31. for (i = 0; i < sz; i++)
  32. {
  33. printf("%d ", arr[i]);
  34. }
  35. printf("\n");
  36. return 0;
  37. }

方法就是在每次冒泡后,检验一下到底这趟冒泡排序有没有交换顺序,如果没有的话,那么flag的值没有发生变化,就可以直接退出循环,这种方法可以略微提升一下效率。 

5.实现冒泡排序函数

用函数实现冒泡排序,传参方法跟数组传参相同,具体可参考C语言函数详解​​​​​​

里面有具体介绍数组传参的方法,这里就直接上代码

  1. #include<stdio.h>
  2. void Bubble_Sort(int arr[], int sz)
  3. {
  4. int flag = 0;
  5. int i = 0;
  6. for (i = 0; i < sz - 1; i++)
  7. {
  8. int j = 0;
  9. for (j = 0; j < sz - 1 - i; j++)
  10. {
  11. if (arr[j] > arr[j + 1])
  12. {
  13. int tmp = arr[j];
  14. arr[j] = arr[j + 1];
  15. arr[j + 1] = tmp;
  16. flag++;
  17. }
  18. }
  19. if (flag == 0)
  20. break;
  21. }
  22. }
  23. int main()
  24. {
  25. int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
  26. int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
  27. int i = 0;
  28. printf("排序前的数组:");
  29. for (i = 0; i < sz; i++)
  30. {
  31. printf("%d ", arr[i]);
  32. }
  33. printf("\n");
  34. Bubble_Sort(arr, sz);
  35. printf("排序后的数组:");
  36. for (i = 0; i < sz; i++)
  37. {
  38. printf("%d ", arr[i]);
  39. }
  40. printf("\n");
  41. return 0;
  42. }

在这里插入图片描述

本文收录于基础算法 、C语言学习专题 、水火莲花-C疑难专题

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/806114
推荐阅读
相关标签
  

闽ICP备14008679号