冒泡排序與插入排序比較
加入技術(shù)交流群
int main( )
本文引用地址：http://www.antipu.com.cn/article/201608/295561.htm{
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è)測(cè)試，在1K元算會(huì)怎樣?我們可以設(shè)計(jì)一個(gè)完全逆序的數(shù)組，元素?cái)?shù)量1000，值從1000-1。首先測(cè)試插入排序。
代碼如下：
#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。
接下來測(cè)試插入排序。代碼如下：
#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)于冒泡。
評(píng)論