首页 > 代码库 > 排序算法

排序算法

一、冒泡排序

1、原理:两两比较,将较大或者较小的数据上浮,实现升序或者降序。

2、实现代码

 1 #include<stdio.h>
 2 void BubbleSort(int *p,unsigned int leng);
 3 int main()
 4 {
 5     int i;
 6     int a[]={1,3,5,7,2,4,6,8};
 7     BubbleSort(a,8);
 8     for(i=0;i<8;i++)
 9     printf("%d ",a[i]);
10     return 0;
11 }
12 void BubbleSort(int *p,unsigned int leng)
13 {
14     int i,j;
15     int temp;
16     for(i=0;i<leng;i++)
17     {
18         for(j=0;j<leng-i-1;j++)
19         {
20             if( (*(p+j)) >= (*(p+1+j)) ) 
21             {
22                 temp=(*(p+j));
23                 (*(p+j))=(*(p+1+j));
24                 (*(p+1+j))=temp;
25             }
26         }
27     }
28 }

3、算法分析

  时间复杂度分析

  最好的情况下是正序,一趟扫描即可完成排序,所需的比较次数和移动次数分别为:技术分享 , 技术分享 。所以,冒泡排序最好的时间复杂度为 技术分享 。

  最坏的情况下是反序,需要进行n-1趟排序,所需的比较次数和移动次数分别为:技术分享

技术分享冒泡排序的最坏时间复杂度为
 技术分享 
  综上,因此冒泡排序总的平均时间复杂度为 技术分享 。

 

排序算法