亲宝软件园·资讯

展开

C语言数组冒泡排序 C语言对数组元素进行冒泡排序的实现

人气:0
想了解C语言对数组元素进行冒泡排序的实现的相关内容吗,在本文为您仔细讲解C语言数组冒泡排序的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言数组冒泡排序,C语言,数组元素排序,下面大家一起来学习吧。

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

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

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

整个排序过程就好像气泡不断从水里冒出来,最大的先出来,次大的第二出来,最小的最后出来,所以将这种排序方式称为冒泡排序(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] 上。
。。。。。。
以此类推,直到整个数组从小到大排序。

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

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

运行结果:
1 2 3 4 5 6 7 8 9 10

优化算法

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

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

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

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

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

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

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

加载全部内容

相关教程
猜你喜欢
用户评论