同事設計一款產品的軟件系統結束了。但是最后幾天發現系統不能使用，好像是看門狗一直復位。我試著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;
}
}
}
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 = %d\n", SWAP_COUNT);
printf("COMP_COUNT = %d\n", 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 = %d\n", SWAP_COUNT);
printf("COMP_COUNT = %d\n", 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 = %d\n", SWAP_COUNT);
printf("COMP_COUNT = %d\n", 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 = %d\n", SWAP_COUNT);
printf("COMP_COUNT = %d\n", COMP_COUNT);
return 0;
}
運行結果如下：
冒泡**次數1498500，比較次數499500。插入**次數501498，比較次數499500。
比較次數相同。**次數冒泡次數很多。是插入排序的2.99倍。所以插入排序優于冒泡。