快速排序算法和二分搜尋算法

本文來自：http://blog.csdn.net/shendl/article/details/4053853     

         算法主要分為排序算法、搜尋算法、圖算法。圖算法我用得不多，沒有發言權，本文就不說了。

         排序算法中最快的是快速排序算法，搜尋算法中最快的是二分搜尋算法。我也最喜歡這2個算法。

         因為，它們是使用遞歸實作的，代碼簡潔清晰，效率又非常高。

         根據我的了解，算法的本質就是數學。根據輸入和設定的目标，采用有限的步驟實作輸出。通常，使用計算機實作的算法，都會用到循環，這樣才能發揮計算機高速運算的優勢。

         循環和遞歸是等效的，這已經被科學家所證明。數學上沒有循環，隻有遞歸的概念，是以使用遞歸代替循環表示算法有很多好處：

         1，  遞歸的代碼要比循環簡潔很多，也優雅很多。

         2，  遞歸的代碼可以用數學方式模組化，可以從數學角度驗證其正确性。

         很多函數式語言甚至沒有循環的概念和關鍵字，強迫你使用遞歸來實作循環。如，ErLang。

         遞歸也有一些缺點，遞歸使用棧來儲存函數位址和參數、傳回值，而棧是有一定大小的，過多的遞歸調用可能會造成棧溢出。

         但是，遞歸算法會容易轉變為循環。我更欣賞遞歸的簡潔，除非真的出現棧溢出的問題，我是不會使用循環的。

二分搜尋算法

理論：

         二分搜尋算法用于針對已排序的集合進行搜尋。

         它的原理是：

         1，  找到排序數組的中間元素，如果它比對目标值，那麼就傳回它在數組中的索引。

         2，  如果沒有找到，那麼判斷中間值比目标值大還是小，

                 如果中間值比目标值大，那麼就對第一個元素到middle-1的元素遞歸這個過程。

                 如果中間值比目标值小，那麼就對middle+1到最後一個元素。

         3，  如果結束的索引小于開始的索引，傳回-1，表示沒有找到。

         4，  如果子集合有2個元素，那麼各自比較。因為Java的整數除法會舍棄小數，如果數組隻有2個元素，那麼middle值一直都是第一個元素。

         經過上述的遞歸過程，最終将傳回比對元素的索引，或者是-1，表示找不到。 

         二分搜尋算法之是以速度快，是因為它每次可以把數組切分成兩半，每次遞歸調用都能去除一半資料，而不用比對每一個資料。

代碼：

         下面是代碼，邏輯清楚，代碼簡單。

    public static int binarySearch(int[] array,int start,int end,int value){

       int middle=(start+end)/2;

       if(end<start){

           return -1;

       }

       if(end==(start+1)){

           if(array[start]==value){

              return start;

           }else if(array[end]==value){

              return end;

           }

       }else if(array[middle]==value){

           return middle;

       }else if(value>array[middle]){

           return binarySearch(array,middle+1,end,value);

       }else if(value<array[middle]){

           return binarySearch(array,start,middle-1,value);

       }

       return -1;

    }

         上述代碼稍加改變，就可以排序任意類型。如使用泛型，然後加上對Comparable接口的實作，即可。

快速排序算法

         二分搜尋算法确實非常快，但是它隻能用于已排序數組。如果數組未排序呢，該怎麼辦呢？簡單，先用快速排序算法進行排序，然後再用二分搜尋進行搜尋。

         先排序再搜尋，要比比對每一個元素快得多。搜尋引擎，資料庫索引也都使用了對資料集合的排序技術，這樣搜尋資料才會快速。

理論：

         最慢，也是最容易想到的排序算法是插入排序算法：

         1，  周遊數組，找出最小的元素，把它放到第一個元素。

         2，  循環查找未排序的數組，直到整個數組排序。

         這需要2個嵌套的循環，意味着它的效率是O(n^2);

         之是以插入排序的效率如此之地，是因為要找出整個數組中最小的資料，需要周遊整個數組的元素。

          而快速排序聰明就聰明在它不查找整個數組最小、次小…的元素，而是每次僅僅把小于某個元素的值移到一邊，通過疊代最終自動實作排序。這就大大節約了排序所需的計算步驟。 

         快速排序算法的理論：

         1，  如果S中的元素個數是0或者1，那麼傳回。

         2，  選取S中的任一進制素v，稱為中心點。

         3，  将S集合中的元素分為2個部分：L={小于pivot 的元素+ pivot }和R={大于或者等于pivot的元素}。

         4，  傳回L和R。

         我們使用Java使用的是就地排序的方式，是以不需要傳回值。

         因為Java是一種可以修改變量的語言，用函數式語言的術語來說，就是有“副作用”。我們利用這個副作用直接修改作為參數的Array，不需要傳回值。

代碼：

    public static void quickSort(int[] array,int start,int end){

       //有可能造成start>end   因為遞歸調用時j+1，可能引起j比end還大1。  另外如果數組是空的，或者輸入錯誤也會出現這種情況

       if(end<=start){

           return;          

       }else {

           //取中間元素為中心點，然後移到最右邊

           int sign=(start+end)/2;

           int tmp=array[end];

           array[end]=array[sign];

           array[sign]=tmp;

           int j=start;

           for(int i=start;i<=end-1;i++){ 

              //小于的元素和标記互換，等于的不能互換，否則會形成死循環

              if(array[i]<array[end])  {                

                   tmp=array[i];

                   array[i]=array[j];

                   array[j]=tmp;

                   j=j+1;

              }         

           }

           //把标記元素和第一個>=它的元素位置互換，這樣數組就分成2個部分，一個部分比中心值小，一個部分比中心值大。

           tmp=array[j];

           array[j]=array[end];

           array[end]=tmp;

           quickSort(array,start,j);

           quickSort(array,j+1,end);

       }

    }

         Java的Arrays類也使用快速排序算法進行排序。但它的代碼寫得像天書一樣。 

         提高快速排序算法執行效率的主要方法是對中心點進行檢測，希望選中的中心點有更大的機率是整個數組的中值。

         我的實作中簡單的選擇數組中間的值作為中心點，一般來說這樣的選擇效率還是不錯的。 

         注意上面的一項實作技術，我們使用把中心資料元素移到數組最後的方式實作了數組的就地比較。這是比較常用的技術，把資料移到數組的最前面或者最後面，友善比較資料。 

         另外，我的Java快速排序代碼使用了“副作用”，而在純函數式語言，如Haskell,ErLang中是沒有“副作用”的，也就是說變量不可以重新指派。此時就需要傳回值，每次都建立新的子數組。但函數式語言的數組處理功能很強，也會做很多性能優化，是以函數式語言實作快速排序代碼更加簡單，沒有“副作用”，也更加數學化。 

         JDK使用二分搜尋和快速排序算法實作搜尋和排序，足見上述兩個算法的性能優勢。