Linux基础30-C语言篇之冒泡排序【入门级】

数组的典型应用：冒泡排序

向后冒泡

• 思想：
  • 一次只排好一个数，针对n个数，最差情况需要n-1次就可以排好
  • 每次排序将相邻数据两两比较，将较大或者较小的数据向后交换，等所有数据比较完成，较大或者较小的数就会出现在最后，这也是该数应该有的位置
  • 在余下的数中，再次应用第2步的操作，直到只剩下1个数。

向前冒泡

• 思想：
  • 一次只排好一个数，针对n个数，最差情况需要n-1次就可以排好
  • 每次排序假定第一个元素是最大或者最小的，用第一个元素的后面的元素一一与第一个元素比较，遇到较大或者较小的和第一个元素交换，访问完数组的最后一个元素，就排好了一个数
  • 在余下的数中，再次应用第2步的操作，直到只剩下1个数。

向前冒泡

原始数列：12345->54321

排序轮数：51234-54123-54312-54321得到：轮数=元素个数-1=4

比较次数：

​ ①1 2 3 4 5 → 5 1 2 3 4（第1轮比4次）5 -1 -0= 4 5-0

​ ② 1 2 3 4 5 → 5 41 2 3（第2轮比3次）5 - 1 -1 = 3 5 -1

​ ③ 1 2 3 4 5 → 5 4 3 1 2 （第3轮比2次）5 -1 -2 = 2 5-2

​ ④ 1 2 3 4 5 → 5 4 3 2 1 （第4轮比1次）5 - 1 -3 = 1 5-3

​ 得到每一轮的比较次数：每一轮比较次数 = 元素个数 - 1 - 轮数，轮数从0开始

代码：

 #include <stdio.h>
 int main(int argc,char *argv[])
 {
    // 创建一个数组，用来存储排序的序列
    int arr[10];
    // 定义三个变量 i:比较的轮数（0～len-1）j：每一轮比较的次数（0～len-1-i）temp：临时变量，用来实
现两个变量值的交换
    int i,j,temp;
    printf("请输入10个整数:\n");
    // 计算数组的大小
    int len = sizeof(arr) / sizeof(arr[0]);
    // 通过循环录入数据
    for(i = 0; i < len; i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("\n");
    // 冒泡排序
    // 第一次循环：控制比较的轮数：轮数 = len -1;
    for(i = 0; i < len - 1; i++)
    {
        // 第二层循环：控制每一轮的比较次数：次数 = len - 1 - i
        for(j = 0; j < len - 1 - i; j++)
        {
            // 相邻两个数进行比较，满足条件交换位置
            if(arr[j] > arr[j+1])  // 1 2
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
     printf("冒泡排序后的数列：\n");
     for(i = 0; i < len; i++)
     {
         printf("%4d",arr[i]);
     }
     printf("\n");
     return 0;
 }