冒泡排序与插入排序比较

　　同事设计一款产品的软件系统结束了。但是最后几天发现系统不能使用，好像是看门狗一直复位。我试着debug一下，发现确实是看门狗复位造成的。在以前同事一直关闭关闭看门狗，在完成所有功能后才打开的看门狗。所以现在才发现看门狗复位。尽量延长看门狗复位时间没有任何效果。所以肯定是某个函数运行时间太长造成了看门狗复位。在浏览程序后我发现他使用了冒泡排序：

　　void bubbleSort( int sort[], unsigned char len )

　　{

　　char i,j;

　　int temp;

　　len -= 2;

　　for( i =len; i>=0; i--)

　　{

　　for( j =0; j<=i; j++)

　　{

　　if( sort[j+1] < sort[j])

　　{

　　temp = sort[j];

　　sort[j]=sort[j+1];

　　sort[j+1]=temp;

　　}

　　}

　　}

　　}

　　这是一个典型冒泡排序。如果按照最极端的情况，排序数组sort恰好是反向那么关键字比较次数为n(n-1)/2。移动次数3n(n-1)/2。所以该算法的时间复杂度应该为n*n。我怀疑是冒泡排序引起的复位后，我屏蔽了该函数运行，产品可以正常运行了。时间比较紧，系统不能做大的修改，那就只好更换排序算法了。于是我建议采用插入排序，问题就解决了。产品很快投产上市了。

　　代码如下：

　　void insert_sort(int a[],int n)

　　{

　　int i,j;

　　int temp;

　　for ( i=1; i

　　{

　　temp=a[i]; //把待排序元素赋给temp，temp在while循环中并不改变，这样方便比较，并且它是 //要插入的元素

　　j=i-1;

　　//while循环的作用是将比当前元素大的元素都往后移动一个位置

　　while ((j>=0)&& (temp

　　a[j+1]=a[j];

　　j--; // 顺序比较和移动,依次将元素后移动一个位置

　　}

　　a[j+1]=temp;//元素后移后要插入的位置就空出了，找到该位置插入

　　}

　　}

　　我认为是一位插入排序的算法时间效率优于冒泡排序。最近在翻看《数据结构》发现书中介绍冒泡与插入排序的时间都是n*n,也就是n的平方。难道是冒泡和插入排序效率是一样的。但是问题为什么解决了，一年多上市销售也没有发现问题。我们的细细研究一下。

　　排序的最极端情况是逆序，那么就采用逆序来测试一下两种算法。平台使用VC6.0。

　　#include

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

　　void bubble_sort(int a[], int n)

　　{

　　int i, j, temp;

　　for (j = 0; j < n - 1; j++)

　　for (i = 0; i < n - 1 - j; i++)

　　{

　　if(a[i] > a[i + 1])

　　{

　　temp = a[i];

　　a[i] = a[i + 1];

　　a[i + 1] = temp;

　　}

　　}

　　}

　　int main( )

　　{

　　int i;

　　int sort[6]={5,4,3,2,1,0};

　　bubble_sort( sort, sizeof( sort)/sizeof(int) );

　　for( i =0 ; i < sizeof( sort)/sizeof(int); i++ )

　　{

　　printf( " %d ", sort[i]);

　　}

　　printf("n");

　　return 0;

　　}

　　我们使用一个完全逆序的数组作为测试样本。sort[6] = {5,4,3,2,1,0}; 程序运行结果完全正确，从小到大排序。

　　我们可以在bubble_sort(int a[], int n)添加代码统计出比较次数和**次数。

　　#include

　　int COMP_COUNT = 0;

　　int SWAP_COUNT = 0;

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

　　void bubble_sort(int a[], int n)

　　{

　　int i, j, temp;

　　for (j = 0; j < n - 1; j++)

　　for (i = 0; i < n - 1 - j; i++)

　　{

　　COMP_COUNT++;

　　if(a[i] > a[i + 1])

　　{

　　SWAP_COUNT +=3; //**计数器

　　temp = a[i];

　　a[i] = a[i + 1];

　　a[i + 1] = temp;

　　}

　　}

　　}