排序算法01------------------------------------冒泡排序
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 版权协议，转载请附上原文出处链接和本声明。