冒泡排序與插入排序比較

　　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;

　　}

　　運(yùn)行結(jié)果

　　使用冒泡比較次數(shù)是15，**次數(shù)45。

　　當(dāng)然也可以采用同樣辦法獲得插入排序比較次數(shù)和**次數(shù)。代碼如下：

　　#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循環(huán)中并不改變，這樣方便比較，并且它是 //要插入的元素

　　j=i-1;

　　//while循環(huán)的作用是將比當(dāng)前元素大的元素都往后移動(dòng)一個(gè)位置

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

　　SWAP_COUNT++;

　　COMP_COUNT++;

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

　　j--; // 順序比較和移動(dòng),依次將元素后移動(dòng)一個(gè)位置

　　}

　　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;

　　}

　　運(yùn)行結(jié)果如下：

　　使用插入比較次數(shù)是25，**次數(shù)15。

　　冒泡比較次數(shù)是15，**次數(shù)45。所以盡管資料介紹他們時(shí)間復(fù)雜度都是n的平方。

　　但是在6個(gè)元素時(shí)插入排序明顯優(yōu)于冒泡。

　　我們可以做一個(gè)測試，在1K元算會(huì)怎樣?我們可以設(shè)計(jì)一個(gè)完全逆序的數(shù)組，元素?cái)?shù)量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循環(huán)中并不改變，這樣方便比較，并且它是要插入的元素

　　j=i-1;

　　//while循環(huán)的作用是將比當(dāng)前元素大的元素都往后移動(dòng)一個(gè)位置

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

　　SWAP_COUNT++;

　　COMP_COUNT++;

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

　　j--; // 順序比較和移動(dòng),依次將元素后移動(dòng)一個(gè)位置

　　}

　　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; //**計(jì)數(shù)器

　　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;

　　}

　　運(yùn)行結(jié)果如下：

　　插入**次數(shù)501498，比較次數(shù)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循環(huán)中并不改變，這樣方便比較，并且它是 //要插入的元素

　　j=i-1;

　　//while循環(huán)的作用是將比當(dāng)前元素大的元素都往后移動(dòng)一個(gè)位置

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

　　SWAP_COUNT++;

　　COMP_COUNT++;

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

　　j--; // 順序比較和移動(dòng),依次將元素后移動(dòng)一個(gè)位置

　　}

　　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; //**計(jì)數(shù)器

　　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;

　　}

　　運(yùn)行結(jié)果如下：

　　冒泡**次數(shù)1498500，比較次數(shù)499500。插入**次數(shù)501498，比較次數(shù)499500。

　　比較次數(shù)相同。**次數(shù)冒泡次數(shù)很多。是插入排序的2.99倍。所以插入排序優(yōu)于冒泡。