《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 業界動態 > 冒泡排序與插入排序比較

冒泡排序與插入排序比較

2017-07-03

       同事設計一款產品的軟件系統結束了。但是最后幾天發現系統不能使用,好像是看門狗一直復位。我試著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}; 程序運行結果完全正確,從小到大排序。

911b931ae29f4263b748fb82fc6db597.JPG

  我們可以在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;

  }

  運行結果

bb4980a0de940d009e1c993dff1254a1.JPG

  使用冒泡比較次數是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;

  }

  運行結果如下fc6913a1eef79210ff17767fb784590c.JPG

  使用插入比較次數是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。

b262cbd30881ea8c42034027a9417460.JPG

  接下來測試插入排序。代碼如下:

  #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;

  }

  運行結果如下:

89e1e2ea1d53ba67039cbf492c2c9e48.JPG

  冒泡**次數1498500,比較次數499500。插入**次數501498,比較次數499500。

  比較次數相同。**次數冒泡次數很多。是插入排序的2.99倍。所以插入排序優于冒泡。


本站內容除特別聲明的原創文章之外,轉載內容只為傳遞更多信息,并不代表本網站贊同其觀點。轉載的所有的文章、圖片、音/視頻文件等資料的版權歸版權所有權人所有。本站采用的非本站原創文章及圖片等內容無法一一聯系確認版權者。如涉及作品內容、版權和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當措施,避免給雙方造成不必要的經濟損失。聯系電話:010-82306118;郵箱:aet@chinaaet.com。
热re99久久精品国产66热_欧美小视频在线观看_日韩成人激情影院_庆余年2免费日韩剧观看大牛_91久久久久久国产精品_国产原创欧美精品_美女999久久久精品视频_欧美大成色www永久网站婷_国产色婷婷国产综合在线理论片a_国产精品电影在线观看_日韩精品视频在线观看网址_97在线观看免费_性欧美亚洲xxxx乳在线观看_久久精品美女视频网站_777国产偷窥盗摄精品视频_在线日韩第一页
  • <strike id="ygamy"></strike>
  • 
    
      • <del id="ygamy"></del>
        <tfoot id="ygamy"></tfoot>
          <strike id="ygamy"></strike>
          国产性猛交xxxx免费看久久| 亚洲午夜电影| 亚洲欧洲另类国产综合| 国产精品高清一区二区三区| 亚洲第一精品电影| 欧美美女操人视频| 欧美一区二区三区免费大片| 国产日韩精品视频一区二区三区| 99精品免费视频| 亚洲黄色高清| 亚洲一区二区精品| 欧美一级久久久久久久大片| 亚洲欧美国产77777| 国产精品日韩欧美一区二区三区| 激情久久五月| 欧美日韩在线播放一区二区| 国内久久精品视频| 亚洲福利免费| 欧美日韩视频在线观看一区二区三区| 欧美日韩亚洲精品内裤| 在线一区免费观看| 欧美在线观看www| 欧美日韩视频在线观看一区二区三区| 久久国产欧美精品| 国产日韩精品久久| 另类尿喷潮videofree| 欧美高清在线视频观看不卡| 在线观看欧美视频| 在线日韩中文字幕| 欧美日韩ab| 在线视频欧美精品| 日韩一区二区精品| 国产欧亚日韩视频| 嫩草国产精品入口| 亚洲欧美国产精品专区久久| 先锋影音网一区二区| 国产精品视频免费一区| 一区二区三区免费观看| 在线看欧美视频| 久久国产日本精品| 亚洲人成人一区二区在线观看| 日韩视频中午一区| 久久综合九色九九| 欧美在线你懂的| 亚洲欧美电影在线观看| 精品成人国产在线观看男人呻吟| 欧美在线日韩精品| 久久久亚洲影院你懂的| 亚洲午夜未删减在线观看| 欧美不卡一区| 国产亚洲欧美一区二区| 亚洲欧美日韩国产一区| 欧美精品日韩www.p站| 在线一区日本视频| 欧美精品在欧美一区二区少妇| 激情一区二区三区| 一本久道久久综合中文字幕| 欧美成人精品在线视频| 欧美黄色小视频| 黄色日韩精品| 亚洲激情中文1区| 久久婷婷丁香| 国产一区成人| 久久成人精品无人区| 欧美另类人妖| 久久天天综合| 日韩亚洲国产精品| 久久亚洲春色中文字幕久久久| 午夜在线一区| 亚洲黄色尤物视频| 国产美女诱惑一区二区| 国产欧美日韩精品在线| 国产精品激情偷乱一区二区∴| 一区二区亚洲| 欧美中文字幕第一页| 亚洲美女视频在线免费观看| 一区二区三区国产| 亚洲国产日韩欧美一区二区三区| 亚洲欧美在线看| 欧美日韩一区二区在线视频| 亚洲午夜精品国产| 午夜精品久久久| 亚洲第一在线综合在线| 亚洲巨乳在线| 亚洲黄色成人久久久| 欧美午夜免费影院| 欧美午夜精品伦理| 最新国产成人av网站网址麻豆| 亚洲一区网站| 国产精品久久久久久亚洲调教| 黄色精品在线看| 欧美在线视频观看| 国产欧美日韩高清| 欧美一区二区日韩| 欧美有码在线观看视频| 1000部精品久久久久久久久| 国产精品影音先锋| 在线观看欧美精品| 国产一区二区主播在线| 国产精品一卡二卡| 国产精品v日韩精品v欧美精品网站| 狠狠色丁香婷婷综合久久片| 在线精品国产成人综合| 国产乱码精品一区二区三区忘忧草| 亚洲在线中文字幕| 久热国产精品视频| 国产精品一区二区三区四区五区| 国产精品久久久久三级| 国产精品久久久一本精品| 国产精品成人在线| 欧美精品三级日韩久久| 欧美日韩一级片在线观看| 亚洲午夜精品| 欧美激情欧美狂野欧美精品| 亚洲一区二区三区高清不卡| 在线免费精品视频| 亚洲第一视频| 亚洲综合久久久久| 国产一区二区精品久久| 在线免费观看视频一区| 你懂的国产精品永久在线| 国产精品成人免费| 国产精品乱子久久久久| 狠狠操狠狠色综合网| 久久在线免费| 久久精品99国产精品酒店日本| 亚洲国产天堂久久国产91| 欧美日韩国产三级| 国产精品一区二区久久久| 久久免费观看视频| 欧美xxx成人| 欧美激情亚洲精品| 国产一区高清视频| 欧美一区二区三区视频免费播放| av成人免费在线观看| 国产午夜精品理论片a级大结局| 亚洲午夜免费福利视频| 久久国产精品99久久久久久老狼| 国产精品综合不卡av| 欧美—级在线免费片| 伊人成年综合电影网| 欧美日韩国产综合视频在线观看| 久久九九国产精品| 国内久久精品视频| 女人香蕉久久**毛片精品| 欧美激情欧美狂野欧美精品| 欧美电影在线观看| 欧美日韩亚洲一区二区| 久久久久久综合网天天| 欧美一区久久| 亚洲在线视频网站| 亚洲一区二区三区四区五区黄| 亚洲欧美日韩一区二区在线| 激情欧美日韩| 亚洲——在线| 欧美在线三区| 亚洲丝袜av一区| 欧美激情精品| 午夜精品久久久久久久| 蜜臀av性久久久久蜜臀aⅴ| 久久综合久色欧美综合狠狠| 亚洲综合色激情五月| 亚洲国产精品久久久久婷婷884| 正在播放欧美一区| 久久婷婷国产麻豆91天堂| 国产婷婷成人久久av免费高清| 欧美激情精品久久久久| 亚洲深夜激情| 久久艳片www.17c.com| 一本色道**综合亚洲精品蜜桃冫| 久久精品日韩一区二区三区| 亚洲国产一区在线| 欧美一区二区精品| 国产日韩视频一区二区三区| 欧美国产极速在线| 亚洲精品欧美在线| 久久久精品一品道一区| 国产一区二区三区视频在线观看| 欧美三日本三级少妇三2023| 久久免费观看视频| 在线亚洲高清视频| 亚洲第一精品在线| 久久久一本精品99久久精品66| 一本色道久久综合亚洲精品不卡| 国产日韩成人精品| 欧美专区福利在线| 国产精品视频九色porn| 欧美视频你懂的| 国产欧美在线看| 韩国福利一区| 欧美国产欧美亚洲国产日韩mv天天看完整| 久久精品国产免费看久久精品| 在线视频日本亚洲性| 亚洲少妇中出一区| 亚洲综合三区| 久久精品日韩| 欧美精品日韩| 欧美韩日一区二区| 136国产福利精品导航网址| 久久成人国产| 欧美亚洲一级片| 免费精品99久久国产综合精品| 国产日韩欧美视频在线| 亚洲欧美日韩精品久久亚洲区| 久久精品国产第一区二区三区| 国产精品毛片高清在线完整版| 欧美搞黄网站| 欧美午夜精品久久久久久超碰| 国产精品igao视频网网址不卡日韩| 国产欧美精品| 国产精品一区二区视频| 夜夜嗨一区二区| 欧美日韩一区不卡| 亚洲宅男天堂在线观看无病毒| 欧美激情第五页| 国产视频精品xxxx| 亚洲成色777777女色窝| 欧美成人官网二区| 欧美天天视频| 精品成人在线观看| 久久午夜视频| 亚洲电影网站| 亚洲人体影院| 亚洲精品永久免费| 99精品视频免费全部在线| 欧美色视频在线| 黄色成人av网站| 麻豆成人综合网| 精东粉嫩av免费一区二区三区| 亚洲视频一区二区在线观看| 亚洲国产视频一区二区| 国产视频亚洲精品| 欧美伦理影院| 亚洲欧美日韩一区在线| 欧美久久久久久久| 欧美成人综合在线| 欧美日韩亚洲视频| 香蕉久久国产| 久久国产精品99久久久久久老狼| 欧美a级在线| 艳妇臀荡乳欲伦亚洲一区| 久久综合色一综合色88| 久久网站热最新地址| 99re热这里只有精品免费视频| 欧美日韩精品一区二区在线播放| 国产精品99久久不卡二区| 亚洲女ⅴideoshd黑人| 久久综合一区| 欧美深夜影院| 欧美精品99| 国产精品午夜av在线| 久久精品亚洲| 欧美区高清在线| 韩国av一区二区三区| 极品中文字幕一区| 久久精品在线播放| 国产精品一区二区三区免费观看| 农夫在线精品视频免费观看| 国产精品va在线| 欧美大胆成人| 在线观看精品视频| 欧美精品久久久久久久久老牛影院| 国产精品激情偷乱一区二区∴| 亚洲主播在线| 久久久久久伊人| 亚洲国产老妈| 国产精品一卡二卡| 亚洲精品欧洲| 亚洲精品乱码久久久久久蜜桃麻豆| 亚洲欧美日韩一区| 国产精品美腿一区在线看| 欧美体内she精视频在线观看| 99www免费人成精品| 亚洲二区免费| 久久久777| 欧美天天综合网| 国产精品拍天天在线| 国产精品网站在线| 国产性天天综合网| 在线观看欧美日本| 在线欧美小视频| 在线观看欧美日本| 欧美日韩精品一区视频| 欧美日韩国产精品自在自线| 亚洲一区二区三区国产| 欧美视频三区在线播放| 99riav久久精品riav| 亚洲在线电影| 亚洲精品一区二区三区婷婷月| 狠狠色综合日日| 久久久久国产成人精品亚洲午夜| 韩国av一区二区| 狠狠88综合久久久久综合网| 欧美深夜影院| 亚洲天堂av电影| 一本一道久久综合狠狠老精东影业| 久久狠狠亚洲综合| 亚洲高清电影| 欧美一区二区视频免费观看| 国产精品久久久一区二区| 免费视频一区二区三区在线观看| 经典三级久久| 樱花yy私人影院亚洲| 久久一区激情| 久久精品99国产精品| 欧美日韩一区二区免费在线观看| 国产免费成人av| 午夜亚洲性色视频| 欧美日韩中文字幕精品| 好吊妞**欧美| 国产欧美精品日韩区二区麻豆天美| 在线观看视频免费一区二区三区| 一本久久a久久免费精品不卡| 亚洲黄色在线| 国产日韩欧美黄色| 亚洲国产精品久久精品怡红院| 久久久久国产一区二区三区四区| 欧美成人一区二区三区在线观看| 91久久久国产精品| 欧美顶级大胆免费视频| 亚洲精品美女久久7777777| 国产精品高潮呻吟| 制服丝袜激情欧洲亚洲| 久久久久久久久久久久久女国产乱| 国产精品国产三级国产aⅴ无密码| 亚洲视频一二| 亚洲一区二区三区四区中文| 国产精品福利在线观看|