经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
C语言实现数组元素排序方法详解
来源:jb51  时间:2023/2/13 8:43:57  对本文有异议

前言

在实际开发中,有很多场景需要我们将数组元素按照从大到小(或者从小到大)的顺序排列,这样在查阅数据时会更加直观,例如:

  • 一个保存了班级学号的数组,排序后更容易分区好学生和坏学生;
  • 一个保存了商品单价的数组,排序后更容易看出它们的性价比。

对数组元素进行排序的方法有很多种,比如冒泡排序、归并排序、选择排序、插入排序、快速排序等,其中最经典最需要掌握的是「冒泡排序」。

以从小到大排序为例,冒泡排序的整体思想是这样的:

  • 从数组头部开始,不断比较相邻的两个元素的大小,让较大的元素逐渐往后移动(交换两个元素的值),直到数组的末尾。经过第一轮的比较,就可以找到最大的元素,并将它移动到最后一个位置。
  • 第一轮结束后,继续第二轮。仍然从数组头部开始比较,让较大的元素逐渐往后移动,直到数组的倒数第二个元素为止。经过第二轮的比较,就可以找到次大的元素,并将它放到倒数第二个位置。
  • 以此类推,进行 n-1(n 为数组长度)轮“冒泡”后,就可以将所有的元素都排列好。

整个排序过程就好像气泡不断从水里冒出来,最大的先出来,次大的第二出来,最小的最后出来,所以将这种排序方式称为冒泡排序(Bubble Sort)。

下面我们以“3 2 4 1”为例对冒泡排序进行说明。

第一轮 排序过程

3 2 4 1 (最初)

2 3 4 1 (比较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,交换)

第二轮结束,次大的数字 3 已经排在倒数第二个位置,所以第三轮只需要比较前两个元素。

第三轮 排序过程

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] 上。

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

具体的代码实现如下所示:

  1. #include<stdio.h>
  2. intmain(){
  3. int nums[10]={4,5,2,10,7,1,8,3,6,9};
  4. int i, j, temp;
  5. //冒泡排序算法:进行 n-1 轮比较
  6. for(i=0; i<10-1; i++){
  7. //每一轮比较前 n-1-i 个,也就是说,已经排序好的最后 i 个不用比较
  8. for(j=0; j<10-1-i; j++){
  9. if(nums[j]> nums[j+1]){
  10. temp = nums[j];
  11. nums[j]= nums[j+1];
  12. nums[j+1]= temp;
  13. }
  14. }
  15. }
  16. //输出排序后的数组
  17. for(i=0; i<10; i++){
  18. printf("%d ", nums[i]);
  19. }
  20. printf("\n");
  21. return0;
  22. }

运行结果:

1 2 3 4 5 6 7 8 9 10

优化算法

上面的算法是大部分教材中提供的算法,其中有一点是可以优化的:当比较到第 i 轮的时候,如果剩下的元素已经排序好了,那么就不用再继续比较了,跳出循环即可,这样就减少了比较的次数,提高了执行效率。

未经优化的算法一定会进行 n-1 轮比较,经过优化的算法最多进行 n-1 轮比较,高下立判。

优化后的算法实现如下所示:

  1. #include<stdio.h>
  2. intmain(){
  3. int nums[10]={4,5,2,10,7,1,8,3,6,9};
  4. int i, j, temp, isSorted;
  5. //优化算法:最多进行 n-1 轮比较
  6. for(i=0; i<10-1; i++){
  7. isSorted =1;//假设剩下的元素已经排序好了
  8. for(j=0; j<10-1-i; j++){
  9. if(nums[j]> nums[j+1]){
  10. temp = nums[j];
  11. nums[j]= nums[j+1];
  12. nums[j+1]= temp;
  13. isSorted =0;//一旦需要交换数组元素,就说明剩下的元素没有排序好
  14. }
  15. }
  16. if(isSorted)break;//如果没有发生交换,说明剩下的元素已经排序好了
  17. }
  18. for(i=0; i<10; i++){
  19. printf("%d ", nums[i]);
  20. }
  21. printf("\n");
  22. return0;
  23. }

我们额外设置了一个变量 isSorted,用它作为标志,值为“真”表示剩下的元素已经排序好了,值为“假”表示剩下的元素还未排序好。

每一轮比较之前,我们预先假设剩下的元素已经排序好了,并将 isSorted 设置为“真”,一旦在比较过程中需要交换元素,就说明假设是错的,剩下的元素没有排序好,于是将 isSorted 的值更改为“假”。

每一轮循环结束后,通过检测 isSorted 的值就知道剩下的元素是否排序好。

到此这篇关于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号