1.排序算法在编程中必不可少，也很常用，是必须要学的。

2.就我本人看来，最适合练习各种算法的语言非C语言不可。C语言本身语法简单直接明了，没有太多的封装，很适合描述算法的各步骤。

一 .冒泡排序

　　1）冒泡排序在排序算法中比较常见，也很简单，适合数据量不是很大的程序，适合日常使用。

　　2）冒泡排序的原理（以升序为例）：将相邻的两个元素进行比较，如果前面的元素比后面的元素大，则两个元素进行交换，否则就进行下两个相邻元素的比较。

　　　　这样进行过一趟的比较，就可以把最大的元素排在最后面了。再对剩下的元素进行同样的操作，即可排序好。这样的排序就像冒泡一样，符合的元素慢慢“浮”到顶端，故名冒泡排序。

　　3）代码如下，已写好注释。

　　

 1 #include<stdio.h>
 2 //arr数组，num 元素个数 
 3 void bubbleSort(int *arr,int num)
 4 {
 5     int i,j;
 6     int temp;
 7     for(i=0;i<num-1;i++)//有num个元素，需要比较num-1次 
 8     {
 9         for(j=0;j<num-i-1;j++)//每一次的比较，需要进行num-i-1次比较， 
10         {                        //这里的i表示已经排序好的元素个数
11                  //升序排序
12             if(arr[j]>arr[j+1])//如果前面的比后面的大，则进行交换 
13             {
14                 temp=arr[j];
15                 arr[j]=arr[j+1];
16                 arr[j+1]=temp;
17             }
18         }
19     }
20 }
21 int main()
22 {    
23     int i; 
24     int arr[10]={1,3,-9,0,10,2,8,9,19,-1};
25     bubbleSort(arr,10);//冒泡排序
26     for(i=0;i<10;i++)
27         printf("%d\n",arr[i]);
28     return 0;
29 }

 

 算法时间复杂度：O(n²)。n个元素，需要n-1次比较，每次比较需要进行n-i-1次比较。

二.拓展

曾经见过一个问题，问：有什么方法可以提升冒泡排序的效率？

答案是：设定一个标志flag,用这个flag表示每一次的比较是否有元素进行交换，如果没有交换，则说明这些元素已经排好序了，那就没必要继续比较下去，算法到此结束。

修改后的bubbleSort如下

 1 void bubbleSort(int *arr,int num)
 2 {
 3     int i,j;
 4     int temp;
 5     int flag=0;//0表示没有交换，1表示有交换 
 6     for(i=0;i<num-1;i++)//有num个元素，需要比较num-1次 
 7     {
 8         for(j=0;j<num-i-1;j++)//每一次的比较，需要进行num-i-1次比较， 
 9         {                        //这里的i表示已经排序好的元素个数
10                  //升序排序
11             if(arr[j]>arr[j+1])//如果前面的比后面的大，则进行交换 
12             {
13                 temp=arr[j];
14                 arr[j]=arr[j+1];
15                 arr[j+1]=temp;
16                 flag=1; 
17             }
18         }
19         if(flag==0)//没有交换，已排好序，直接结束循环 
20             break;
21         flag=0; 
22     }
23 }

 

版权声明：本文为duichoumian原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/duichoumian/p/12530136.html