程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 冒泡排序 兩次優化

冒泡排序 兩次優化

編輯:C++入門知識

(1)bubble sort的定義是:進行n-1次排序,每次排序都要比較所有相鄰的兩個元素,但第i次排序時array尾部的i-1個元素都是排序好的,所以內層循環的長度是n-i。 算法實現如下 [java]   void bubbleSort( int array[]) {          for (int i = 1; i < array. length; ++i ) {                for (int j = 0; j < array. length - i ; ++j) {                      if (array[j] > array[j + 1]) {                            int tmp = array[j];                           array[j] = array[j + 1];                           array[j + 1] = tmp;                     }               }         }   }       (2)一次優化。我們可以想到這種極端情況:array本身就是排序好的,但是依照如上算法,我們仍然要遍歷n平方/2次。原因在於,我們沒有機制檢查數組是否是排序好的。解決辦法就是加入標識項,如果發現一次內層循環沒有經過任何交換,則說明array已經排序完畢。算法實現如下: [java]   void bubbleSort( int array[]) {         boolean exchange = false ;         for (int i = 1; i < array. length; ++i) {               for (int j = 0; j < array. length - i; ++j) {                     if (array[j] > array[j + 1]) {                           int tmp = array[j];                          array[j] = array[j + 1];                          array[j + 1] = tmp;                           exchange = true;                    }              }               if (!exchange) {                     break ;              }        }       (3)二次優化。我們再想象一種極端情況:array長度為n,但是只有0,1元素未排序,那麼依照上一種優化算法我們依然要遍歷2*n次。原因在於我們內層循環長度的設定依據是,i次排序array的後i-1個元素是排序好的,但實際上i次排序的循環長度取決於i-1次排序時最後的交換位置,例如i-1次排序的最後交換位置是index,則表明index之後的元素都已經排序完畢,我們只需要記錄這個Index就得到了下次(i次)的循環長度。算法實現如下: [java]   void bubbleSort( int array[]) {         boolean exchange = false;         int index = 0;         int mark = array.length - 1;         for (int i = 1; i < array. length; ++i) {               for (int j = 0; j < mark; ++j) {                     if (array[j] > array[j + 1]) {                           int tmp = array[j];                          array[j] = array[j + 1];                          array[j + 1] = tmp;                           exchange = true ;                          index = j;                    }              }               if (!exchange) {                     break ;              }              mark = index;        }         summary: 當然這種所謂的優化知識學院派的說法,實際工作中自己的水准在哪個級別上全靠自己。例如我本身就是個菜鳥,所以我向來只是停留在定義級別的bubble sort上。當然,學習的動力也來源於此。比如說這次學習、總結之後,也許還不能夠一下子上升到quick sort的級別,但是起碼可以把優化後的bubble sort運用到工作中去。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved