冒泡排序與插入排序比較

　　同事設計一款產(chǎn)品的軟件系統結束了。但是最后幾天發(fā)現系統不能使用，好像是看門(mén)狗一直復位。我試著(zhù)debug一下，發(fā)現確實(shí)是看門(mén)狗復位造成的。在以前同事一直關(guān)閉關(guān)閉看門(mén)狗，在完成所有功能后才打開(kāi)的看門(mén)狗。所以現在才發(fā)現看門(mén)狗復位。盡量延長(cháng)看門(mén)狗復位時(shí)間沒(méi)有任何效果。所以肯定是某個(gè)函數運行時(shí)間太長(cháng)造成了看門(mén)狗復位。在瀏覽程序后我發(fā)現他使用了冒泡排序：

　　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;

　　}

　　}

　　}

　　}

　　這是一個(gè)典型冒泡排序。如果按照最極端的情況，排序數組sort恰好是反向那么關(guān)鍵字比較次數為n(n-1)/2。移動(dòng)次數3n(n-1)/2。所以該算法的時(shí)間復雜度應該為n*n。我懷疑是冒泡排序引起的復位后，我屏蔽了該函數運行，產(chǎn)品可以正常運行了。時(shí)間比較緊，系統不能做大的修改，那就只好更換排序算法了。于是我建議采用插入排序，問(wèn)題就解決了。產(chǎn)品很快投產(chǎn)上市了。

　　代碼如下：

　　void insert_sort(int a[],int n)

　　{

　　int i,j;

　　int temp;

　　for ( i=1; i

　　{

　　temp=a[i]; //把待排序元素賦給temp，temp在while循環(huán)中并不改變，這樣方便比較，并且它是 //要插入的元素

　　j=i-1;

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

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

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

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

　　}

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

　　}

　　}

　　我認為是一位插入排序的算法時(shí)間效率優(yōu)于冒泡排序。最近在翻看《數據結構》發(fā)現書(shū)中介紹冒泡與插入排序的時(shí)間都是n*n,也就是n的平方。難道是冒泡和插入排序效率是一樣的。但是問(wèn)題為什么解決了，一年多上市銷(xiāo)售也沒(méi)有發(fā)現問(wèn)題。我們的細細研究一下。

　　排序的最極端情況是逆序，那么就采用逆序來(lái)測試一下兩種算法。平臺使用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;

　　}

　　我們使用一個(gè)完全逆序的數組作為測試樣本。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;

　　}

　　}

　　}