冒泡排序与插入排序比较

　　int main( )

　　{

　　int i;

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

　　COMP_COUNT = 0;

　　SWAP_COUNT = 0;

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

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

　　{

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

　　}

　　printf("n");

　　printf("SWAP_COUNT = %dn", SWAP_COUNT);

　　printf("COMP_COUNT = %dn", COMP_COUNT);

　　return 0;

　　}

　　运行结果

　　使用冒泡比较次数是15，**次数45。

　　当然也可以采用同样办法获得插入排序比较次数和**次数。代码如下：

　　#include

　　int COMP_COUNT = 0;

　　int SWAP_COUNT = 0;

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

　　{

　　int i,j;

　　int temp;

　　for ( i=1; i

　　{

　　SWAP_COUNT++;

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

　　j=i-1;

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

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

　　SWAP_COUNT++;

　　COMP_COUNT++;

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

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

　　}

　　SWAP_COUNT++;

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

　　}

　　}

　　int main( )

　　{

　　int i;

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

　　COMP_COUNT = 0;

　　SWAP_COUNT = 0;

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

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

　　{

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

　　}

　　printf("n");

　　printf("SWAP_COUNT = %dn", SWAP_COUNT);

　　printf("COMP_COUNT = %dn", COMP_COUNT);

　　return 0;

　　}

　　运行结果如下：

　　使用插入比较次数是25，**次数15。

　　冒泡比较次数是15，**次数45。所以尽管资料介绍他们时间复杂度都是n的平方。

　　但是在6个元素时插入排序明显优于冒泡。

　　我们可以做一个测试，在1K元算会怎样?我们可以设计一个完全逆序的数组，元素数量1000，值从1000-1。首先测试插入排序。

　　代码如下：

　　#include

　　int COMP_COUNT = 0;

　　int SWAP_COUNT = 0;

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

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

　　void insert_sort(int a[],int n)

　　{

　　int i,j;

　　int temp;

　　for ( i=1; i

　　{

　　SWAP_COUNT++;

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

　　j=i-1;

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

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

　　SWAP_COUNT++;

　　COMP_COUNT++;

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

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

　　}

　　SWAP_COUNT++;

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

　　}

　　}

　　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;

　　}

　　}

　　}

　　int main( )

　　{

　　int i;

　　int sort[1000];

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

　　sort[i] = 999-i;

　　COMP_COUNT = 0;

　　SWAP_COUNT = 0;

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

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

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

　　{

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

　　}

　　printf("n");

　　printf("SWAP_COUNT = %dn", SWAP_COUNT);

　　printf("COMP_COUNT = %dn", COMP_COUNT);

　　return 0;

　　}

　　运行结果如下：

　　插入**次数501498，比较次数499500。

　　接下来测试插入排序。代码如下：

　　#include

　　int COMP_COUNT = 0;

　　int SWAP_COUNT = 0;

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

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

　　void insert_sort(int a[],int n)

　　{

　　int i,j;

　　int temp;

　　for ( i=1; i

　　{

　　SWAP_COUNT++;

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

　　j=i-1;

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

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

　　SWAP_COUNT++;

　　COMP_COUNT++;

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

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

　　}

　　SWAP_COUNT++;

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

　　}

　　}

　　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;

　　}

　　}

　　}

　　int main( )

　　{

　　int i;

　　int sort[1000];

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

　　sort[i] = 999-i;

　　COMP_COUNT = 0;

　　SWAP_COUNT = 0;

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

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

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

　　{

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

　　}

　　printf("n");

　　printf("SWAP_COUNT = %dn", SWAP_COUNT);

　　printf("COMP_COUNT = %dn", COMP_COUNT);

　　return 0;

　　}

　　运行结果如下：

　　冒泡**次数1498500，比较次数499500。插入**次数501498，比较次数499500。

　　比较次数相同。**次数冒泡次数很多。是插入排序的2.99倍。所以插入排序优于冒泡。