冒泡排序与插入排序比较
发布时间：2016-8-25 10:41
发布者：designapp
|
同事设计一款产品的软件系统结束了。但是最后几天发现系统不能使用，好像是看门狗一直复位。我试着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冒泡排序。如果按照最极端的情况，排序数组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 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  我们可以在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 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  使用冒泡比较次数是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  使用插入比较次数是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 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  接下来测试插入排序。代码如下： #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 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  冒泡**次数1498500，比较次数499500。插入**次数501498，比较次数499500。 比较次数相同。**次数冒泡次数很多。是插入排序的2.99倍。所以插入排序优于冒泡。 |
网友评论