【循序搜尋 ( Sequential Search ) 】

循序搜尋演算法 ( 以 C 語言描述 )

　　int seqsearch ( int  list [ ] , int searchnum , int  n )

　　{

　　　int   i ;

　　　list[n] = searchnum ;

　　　for ( i =0 ; list[i] != searchnum ; i++ ) ;

　　　return (( i < n ) ?   i : -1 )

　　}

【二分搜尋 ( Binary Search ) 】

假設串列依鍵值大小排列，使得 list[0].key <= list[1].key <= .....<= list[n-1].key。此法是由比較 searchnum 和 list

[middle] 開始，其中 middle = ( n-1 ) / 2 。其搜尋的結果可能有三種：

１、searchnum < list[middle].key ：

　　此種情況，放棄介於 list[middle] 和 list[n-1] 之間的記錄，繼續搜尋介於 list[0] 和 list[middle - 1] 之間的記

　　錄。

２、searchnum = list[middle].key ：

　　在此種情形下，搜尋成功地結束。

３、searchnum ＞ list[middle].key ：

　　此種情況，放棄介於 list[0] 和 list[middle] 之間的記錄，繼續搜尋介於 list[middle+1] 和 list[n - 1] 之間的記

　　錄。

演算法如下 ( 以 C 語言描述 )

　　int  binsearch ( element  list[ ] , int  searchnum , int  n )

　　{

　　　int  left = 0, right = n-1, middle ;

　　　while  ( left  <= right ) {

　　　　　　middle = ( left + right ) / 2

　　　　　　switch  ( COMPARE ( list[middle].key , searchnum ) ) {

　　　　　　case  -1 : left = middle + 1 ;

　　　　　　　　　  break ;

　　　　　　case   0 : return  middle ;

　　　　　　case   1 : right = middle - 1 ;

　　　　　　}

　　　}

　　　return  -1 ;

　　}

【費式搜尋法】

特性：

　　費式搜尋觀念與二元搜尋相似，只是二元搜尋每次一分為二，而每費式搜尋是依據費式數列來劃分

　　的。

定義：

　　　Fi = F_i-1 + F_i-2 ，i >= 0 ; F₀ = 0 , F₁ = 1

　　　由上式公式可得費式數列：0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , ....

作法：

　　假設有 n 個記錄 ( record ) ，此數目比某一費式數目少 1 ，即 n = F_k-1。然後第一次比較的鍵值是 KF_k-1

　　。當

　　　　１、 K < K_Fk-1 ：所有找的鍵值落在 1 至 F_k-1 - 1 之間。

　　　　２、 K = K_Fk-1 ：表示找到了。

　　　　３、K ＞K_Fk-1 ：所要找的鍵值落在 F_k-1 + 1 至 F_k-1 之間。

【插補搜尋法】

基本條件：

　　被搜尋檔案的記錄必須為經過排序過的順序性資料。

方法：

　　插補排序不同於二元搜尋法，若我們查字典欲找尋 boy 這個字，通常會大致翻到 b 字頭附近才再往

　　前或往後翻數頁，一直以”多一點”或”少一點”來修正，直到找到為止。只是計算下列運算。

　　　　　i = ( k - k_i ) / ( k_u - k_i )

　　k_i 為最小鍵值，k_u 為最大鍵值。

演算法如下：

　　　int    inter_search  ( int  n,  int  key )　

          {

              if  ( key < data[0].key  ||  key > data[MAX-1].key )

                  return   -1 ;               /*  沒有找到 */

              else

                  return   inter_find ( key, 0 , MAX-1 ) ;     /* 插補搜尋遞迴呼叫 */

           }

          int   inter_find (  int key , int  left ,  int  right )

          {

            int    next_guess ;      /* 下一個可能的索引 */

            int   offset ;               /* 索引位移 */

            int   range ;                /* 鍵值範圍 */

            int    index_range       /* 索引範圍 */

            int   temp ;               

            if  ( data[left].key == key )   /* 找到了*/

                return   left ;

            else

                 /* 沒有找到 */

                 if   ( left == right  ||  data[left].key == data[right].key )

                     return   -1 ;

                 else

                       {

                         index_range = right - left  /* 計算索引範圍 */

                         range   =  data[right].key  -  data[left].key ;

                         offset   =  key - data[left].key  /* 計算鍵值位移 */

                         temp   =  ( offset * index_range )   /* range */

                         next_guess   =  left + temp ; /* 下一個可能的索引 */

                         if   ( next_guess  ==  left  )    /* 已試過 */

                               next_guess ++ ;

                         if   ( key < data[next_guess].key )  /* 進行左半部插補搜尋 */

                               return   inter_find ( key, left, next_guess - 1 ) ;

                         else                                             /* 進行右半部插補搜尋 */

                               return   inter_find ( key, next_guess, right ) ;

                        }

            }

【插入排序 ( Insertion Sort ) 】

作法：

　　　不斷往後拿一筆記錄，插入到前面已經排序好的記錄，亦即是插入一個記錄 R 在一堆已按次序排

　　　好的記錄中，R₁,R₂,R₃ ,...., R_i ( K₁ <= K₂ <= K_i ) 而使得 i + 1 項記錄已經排列妥；並且有一個 Dummy

　　　，以便存放 R[0] = -∞。

插入排序的演算法：

                    void  insertion_sort ( element  list[ ], int n )

                    {

                        int   i, j ;

                        element  next ;

                        for ( i = 1; i < n ; i++ )   {

                              next  =  list[i] ;

                              for  ( j = i - 1 ; j >= 0 && next.key < list[j].key ; j-- )

                                      list[j+1] = list[j];

                              list[j+1] = next ;

                        }

                      }

特性：

　　　１、time  complexity ( 時間複雜度 ) ： worst  case ( 最壞情況 ) 與 average  case ( 平均情況 ) 為 O( n² ) 。

　　　２、需要兩個額外的空間，分別為 Dummy 及交換用的 Save 。

　　　３、是穩定排序 ( stable ) 。

　　　４、對 " 部份排序 " 過的檔案很有效。

範例：

　　　假設 n = 5 且輸入序列為 ( 5 , 4 , 3 , 2 , 1 )。在每一插入步驟之後，序列結果如下：

【快速排序 ( Quick Sort ) 】

快速排序法是一種分而治之( 或切割征服( Divide and conquer) ) 的排序法。其觀念是將待排序的 N 個鍵值分

成左右兩半，左半邊之鍵值小於第一個鍵值，而右半邊則大於或等於第一個鍵值。如所下圖所示：

作法：

　　　１、取第一個記錄的鍵值 K 當做 Control Key 。

　　　２、由左而右，i = 1 , 2 , .... , 找到第一個 Ki ≧K。

　　　　　由右而左，j = n , n - 1 , .... , 1 , 找到第一個 Kj ≦ K。

　　　３、若 i < j 則 Ri 與 Rj 對調位置。

　　　　　否則，R 與 Rj 對調位置，將此檔案一分為二 ( R₁ , R₂ , R₃ , ... , R_i-1 ) 、Rj ( R_j+1 , R_j+2 , ... , R_n )，

　　　　　如此兩個子檔案可獨立的重覆 １到３進行。

快速排序的演算法：

　　　　void  quicksort ( element  list[ ] , int left , int right )

                 {

                    int  pivot , i , j ;

                    element  temp ;

                    if  ( left < right )   {

                         i = left ; j = right + 1 ;

                         pivot = list[left].key ;

                         do  {

                                do  

                                      i ++ ;

                                while  ( list [ i ].key < pivot ) ;

                                do 

                                      j -- ;

                                while ( list [ j ].key > pivot ) ;

                                if  ( i < j )

                                     SWAP ( list[i] , list[j] , temp )

                           }  while ( i < j ) ;

                         SWAP ( list[left] , list[j] , temp ) ;    

                         quicksort ( list , left , n-1 ) ;

                         quicksort ( list , j+1 , right ) ;

                      }

                   }

特性：

　　　１、time  complexity ( 時間複雜度 ) ： worst  case ( 最壞情況 ) 為 O( n² ) 與 average  case ( 平均情況 ) 為

　　　　　O( n log n ) 。

　　　２、在考慮平均執行時間的前題下，快速排序是內部排序最好方法。

　　　３、需要額外的堆疊 ( stack ) 空間。

　　　４、不是穩定排序 ( stable ) 。

範例：

【合併排序 ( Merge Sort ) 】

作法：

　　　合併排序適用於內部排序和外部排序，也是一種典型的「分而治之」的方法，將 N 筆記錄依鍵值

　　　不遞減順序排序的方法為：

　　　１、將 N 個長度為 1 的鍵值成對地合併成 N / 2 個長度為 2 的鍵值組。

　　　２、將 N2 個長度為 2 的鍵值成對地合併成 N / 4 個長度為 4 的鍵值組。

　　　３、將鍵值組成對地合併，直到合併成一組長度為 N 的鍵值組為止。

特性：

　　　１、time  complexity (時間複雜度)： worst  case ( 最壞情況 ) 與 average  case ( 平均情況 ) 為O( n log n ) 。

　　　２、為一穩定排序 ( stable sorting ) 。

【累堆排序 ( Heap Sort ) 】

作法：

　　　１、將檔案 ( x1 , x2 , x3 , ... , xn ) 轉換成完整二元樹。如下圖所示：

　　　２、將完整二元樹轉換成堆積樹 ( heap tree ) 。

　　　３、輸出樹根鍵值。

　　　４、將樹中最後一個節點搬到樹根。

　　　５、重覆步驟 ２ 到 ４，直到輸出所有鍵值為止。

特性：

　　　１、time  complexity ( 時間複雜度 ) ： worst  case ( 最壞情況 )與average  case( 平均情況 ) 為O( n log n ) 。

　　　２、為一種不穩定排序。

　　　３、只需要一個額外的記錄空間。

累堆排序的演算法：

　　　void  heapsort ( element  list[ ] , int  n )

             {

                int  i, j ;

                element   temp ;

                for ( i = n / 2 ; i > 0 ; i -- )  

                       adjust ( list, i, n ) ;

                for ( i = n - 1 ; i > 0 ; i -- )   {

                      SWAP ( list[1], list[j+1], temp ) ;

                      adjust ( list, 1 , i );

                }

               }

【基底排序 ( Radix Sort ) 】

【謝耳排序 ( Shell sort ) 】

作法：

　　將欲排序的元素依某間隔分為數個集合，再逐漸減少這個量直到將元素排序完成。

範例：

　　假設現在有一字元陣列，如下所示：

　　將字串分割成數個集合的方法是從元素總數的 1 / 2 開始為間隔來劃分，而每次均將間隔量除以 2 縮小

　　間隔範圍直到零為止。

謝耳排序的演算法：

              void  shell_sort ( char  *string , int  count )

              {

                  int   pos ;         /* 處理位置 */

                  int   offset ;      /* 位移量 */

                  int   i , j ;

                  char   temp ;

                  offset = count  /  2 ;       /* 建立位移量 */

                  while  ( offset  !=  0 )      /* 處理排序迴路 */

                  {

                       for ( j = offset ; j < count ; j++ )   /* 交換迴路 */

                       {

                           temp = string[i] ;   /* 保留其值 */

                           pos =  j - offset ;   /* 計算處理位置 */

                           while  ( temp < string[pos]  &&  pos >= 0  &&  j <= count )   /* 比較迴路 */

                           {

                                    string [pos+offset]  =  string[pos] ;

                                    pos = pos -offset ;   /* 下一個處理位置 */

                           }

                           string[pos+offset]  =  temp ;

                       }

                       printf ( "輸出結果：[%s]\n”, string ) ;

                       offset = offset / 2 ;

                  }

               }

【氣泡排序 ( Bubble  sort ) 】

作法：

　　氣泡排序的基本作法是對整個資料表做數次的循序處理，在每次處理時，比較某一記錄它後面的記

　　錄鍵值大小，如果它們的次序不對則交換兩記錄的位置，重覆此步驟直到適當位置才停止。

氣泡排序的演算法：

　　　procedure  bubble_sort ( R , n )

             for  x = 1  to   n -1  do

                  begin

                        y = x

                        while  ( y > 0 )  and  ( K_y  >  K_y+1 )   do

                           begin

                                 s = R_y  ;  R_y = R_y+1 ; 

                                 R_y+1 = s ;  y = y -1

                           end

                   end

               end  bubble_sort

特性：

　　１、time  complexity ( 時間複雜度 ) ： worst  case ( 最壞情況 ) 與 average  case ( 平均情況 ) 為 O( n² ) 。

　　２、需要一個額外空間。

　　３、為一種穩定排序 ( stable sorting ) 。

【選擇排序 ( Selective sort ) 】

作法：

　　　設一串記錄為 R₁ , R₂ , R₃ , ... , R_n ，其鍵值分別為 K₁ , K₂ , K₃ , ... , K_n 。將此記錄由小到大排列。

　　　第一步：由所有的記錄中挑選一個具有最小鍵值者，然後將此記錄與第一個記錄對調。

　　　第二步：由剩餘的記錄中挑選次小鍵值的記錄，然後將該筆記錄與第二個記錄對調。

　　　第三步：重覆上述的步驟，直到將所有的記錄排列好為止。

特性：

　　１、time  complexity ( 時間複雜度 ) ： worst  case ( 最壞情況 ) 與 average  case ( 平均情況 ) 為 O( n² ) 。

　　２、需要暫存一筆記錄的額外空間。

　　３、是一種穩定排序 ( stable sorting ) 。

選擇排序的演算法：

         procedure   select_sort ( R , n ) / 此演算法是按鍵值由小到大排列 /

         for   i = 1 to n -1  do

                 begin

                             k = i

                             for  j = i +1 to n  do

                                   if  K_j < K_k  then K = j

                             if  i < > K  then

                                  begin

                                             temp = R_i ; R_i = R_k ; R_k = temp

                                  end

                  end

           end   select_sort