经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
C语言中冒泡排序算法详解
来源:jb51  时间:2022/1/18 11:29:40  对本文有异议

一、算法描述

比较相邻两个元素,如果第一个比第二个大则交换两个值。遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面。假设数组有 n 个元素,那么需要遍历 n - 1 次,因为剩下的一个元素一定是最小的,无需再遍历一次。因此需要两层循环,第一层是遍历次数,第二层是遍历未排序数组。

动图如下:

黄色部分表示已排好序的数组,蓝色部分表示未排序数组

核心代码如下:

  1. /**
  2. * @brief 冒泡排序
  3. *
  4. * @param arr 待排序的数组
  5. * @param size 数组大小
  6. */
  7. static void bubble_sort(int *arr, int size)
  8. {
  9. for (int i = 0; i < size - 1; i++) {
  10. bool swapped = false; // 设置标记,用于检查是否已排好序
  11. for (int j = 0; j < size - i; j++)
  12. if (arr[j] > arr[j + 1]) {
  13. swap(arr + j, arr + j + 1);
  14. swapped = true;
  15. }
  16. if (!swapped) // 未交换则排序完毕,跳出循环
  17. break;
  18. }
  19. }

布尔值 swapped 是一种优化手段,在每次遍历未排序数组之前将其设置为 false 表示还未交换。如果遍历完未排序数组之后其值还是 false 则表示遍历过程种没有发生交换,也就是说数组已经有序,无需再次遍历,跳出循环。

二、算法分析

时间复杂度:O(N2),两层循环

空间复杂度:O(1),交换元素时只用了一个临时变量

最好情况:O(N),有序数组遍历一次后 swapped 为 false 退出循环

最坏情况:O(N2),数组倒序

稳定性:稳定,比较两个元素大小时不包括元素相等的情况,故相等元素的相对位置不变

三、完整代码

  1. /**
  2. * @file bubble_sort.c
  3. * @date 2022-01-16
  4. * @author Pineapple (pineapple_cpp@163.com)
  5. *
  6. * @brief 冒泡排序
  7. */
  8.  
  9. #include <assert.h>
  10. #include <stdbool.h>
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <time.h>
  14.  
  15. /**
  16. * @brief 交换函数
  17. *
  18. * @param left 左边的元素
  19. * @param right 右边的元素
  20. */
  21. static inline void swap(int *left, int *right)
  22. {
  23. int temp = *left;
  24. *left = *right;
  25. *right = temp;
  26. }
  27.  
  28. /**
  29. * @brief 冒泡排序
  30. *
  31. * @param arr 待排序的数组
  32. * @param size 数组大小
  33. */
  34. static void bubble_sort(int *arr, int size)
  35. {
  36. for (int i = 0; i < size - 1; i++) {
  37. bool swapped = false; // 设置标记,用于检查是否已排好序
  38. for (int j = 0; j < size - i; j++)
  39. if (arr[j] > arr[j + 1]) {
  40. swap(arr + j, arr + j + 1);
  41. swapped = true;
  42. }
  43. if (!swapped) // 未交换则排序完毕,跳出循环
  44. break;
  45. }
  46. }
  47.  
  48. /**
  49. * @brief 测试函数
  50. *
  51. */
  52. static void test()
  53. {
  54. const int size = rand() % 500; // 生成随机数组大小
  55. int *arr = (int *)calloc(size, sizeof(int));
  56.  
  57. // 生成范围 -50 到 49 的随机数组
  58. for (int i = 0; i < size; i++)
  59. arr[i] = rand() % 100 - 50;
  60.  
  61. bubble_sort(arr, size);
  62.  
  63. for (int i = 0; i < size - 1; i++)
  64. assert(arr[i] <= arr[i + 1]);
  65.  
  66. free(arr);
  67. }
  68.  
  69. int main(void)
  70. {
  71. srand(time(NULL));
  72. test();
  73. return 0;
  74. }

总结

到此这篇关于C语言中冒泡排序算法详解的文章就介绍到这了,更多相关C语言冒泡排序内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号