一边学算法，一边学c语言之冒泡排序

概要

　　在编程中，我们可能会用到各种各样的算法，其中有些问题的对应的算法有好几种，所以我们要分析一个算法的优劣性，选择合适的算法。

冒泡算法分析

　　基于上述目的，我们需要学会算法分析这门技术，来衡量算法性能，以冒泡算法为例：

　　冒泡算法：“大数下沉，小数上冒”

　　伪代码描述如下(《算法分析与设计》)：

1 BUBBLE-SORT(A)
2 for i <- 1 to length[A]
3     do for j <- lenght[A] downto i+1
4         do if A[j]<A[j-1]
5             then exchange A[j] <->A[j-1]

　　我们给上面的代码加上每行的代码时间开销和执行次数，其中设length[A]=n，第四行的执行次数为 $t_i$ ：

1 BUBBLE-SORT(A)　　　　　　　　　　　　　　　　　　　　　　开销　
2 for i <- 1 to length[A]　　　　　　　　　　　　　　　　 c1　　　　　　　　　　　　　　
3     do for j <- lenght[A] downto i+1　　　　　　　　　c1　　　　　　　　　　　　　　　　　　　　　　　　
4         do if A[j]<A[j-1]　　　　　　　　　　　　　　　 c2
5             then exchange A[j] <->A[j-1]　　　　　　 c3

　　第一行的执行次数为：

　　　　n+1

　　第二行的执行次数为（\sum_{i=1}^{n}(n-i+1)）：

　　　　 $\sum_{i=1}^{n}(n-i+1)$

　　第三行的执行次数为（\sum_{i=1}^{n}(n-i)）：

　　　　 $\sum_{i=1}^{n}(n-i)$

　　那么该算法的总运行时间为，每条语句的开销X语句的执行次数之和：

　　 $T(n)=c_1(n+1)+c_1(\sum_{i=1}^{n}(n-i+1))+c_2(\sum _{i=1}^{n}(n-i))+c_3t_i$

　　　　　 $=c_1(n+1)+c_1\frac{n(n+1)}{2}+c_2\frac{n(n-1)}{2}+c_3t_i$

　　　　 $=\frac{(c_1+c_2)}{2}n^2+\frac{(3{c_1}-c_2)}{2}n+c_1+c_3t_i$

　　算法的最佳情况：

　　　　 $t_i=0$

　　　　 $T(n)=\frac{(c_1+c_2)}{2}n^2 + \frac{(3c_1+c_2)}{2}n+c_1$

　　最坏的情况：

　　　　 $t_i=\sum_{i=1}^{n}(n-i)$ ， $S_n=\frac{(a_1+a_n)n}{2}$

　　　　 $T(n)=\frac{(c_1+c_2+c_3)}n^2+\frac{(3c_1-c_2-c_3)}{n}+c_1$

　　这时 $T(n)$ 可以写成 $an^2+bn+c$

　　增长的数量级：

　　当n很大时，低阶项可以忽略，公式可以简化为： $an^2$

　　最坏的情况下数量级为： $\Theta (n^2)$

　　 $\Theta (n^2)$ 的算法会比 $\Theta (n^3)$ 的算法运行的快

　　开始我是这么写的：

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

　　然后发现了错误，是因为函数参数传递的参数只是一个指针，不能计算数组的大小，于是这么写的:

#include <stdio.h>


void bubble_sort(int a[],int n);


void main()
{
     int a[]={12,3,6,34,4,-44,2,10,44};
     int n=sizeof(a)/sizeof(int);
     bubble_sort(a,n);
     for (int i=0;i<n;i++)
     printf("  %d  ",a[i]);
     printf("\n");
}


void bubble_sort(int a[],int n)
{
     //int n=sizeof(a)/sizeof(int);
     for (int i=0;i<n;i++)
     {
         for (int j=n-1;j>=i+1;j--)
         {
             if (a[j] < a[j-1])
            {
                 int temp=a[j];
                 a[j]=a[j-1];
                 a[j-1]=temp;
             }
         }
     }
}

　　总结：

　　算法分析需要的是每句代码的时间开销和执行次数，在数据很大的时候可以忽略低阶项，我们一般在乎最坏时间复杂度。
　　c语言函数的参数传递的数组形参只是一个地址