組合算法概論(A Brief IntrodUCtion to Combinatorial Algorithm)
    組合算法是算法分析學當中非常重要的一個分支，關于它在計算機科學的地位我就不敖述了，下面為大家整理了整個材料，算法是我收集的，只是分門別類簡單介紹一下，然后把我的材料做了個整理，大家收藏吧，感覺挺有用的，費了我好長時間和精力呀，我現在預備考研了，沒有太多時間發很多經典文章了，這片算是大部頭了。
    關于組合學問題的算法，計算對象是離散的、有限的數學結構。從方法學的角度，組合算法包括算法設計和算法分析兩個方面。關于算法設計，歷史上已經總結出了若干帶有普遍意義的方法和技術，包括動態規劃、回溯法、分支限界法、分治法、貪心法等。下面我們著重談談幾個有代表性的組合算法：
單純形法：
    這是一種線性規劃算法，由G.B.Dantzig在1947年提出，后來由他和其他的學者又提出了單純形法的變形和改進。這些被實踐證實都是行之有效的，線性規劃研究線性目標函數在一組線性等式與線性不等式約束下的極值問題。這本來是連續問題，Dantzig發現線性規劃問題的可行解集（即滿足約束條件的點的全體）是一個超多面體。假如它的最優解存在，那么這個最優解一定可以在超多面體的一個頂點取到。由于超多面體的頂點只有有限個，從而使線性規劃成為一個組和優化問題。單純形法是按照一定的規則，從可行解集的一個頂點轉移到另一個頂點，使得目標函數的值不斷地得到改進，最后達到最優。盡管單純形法一直使用得很好，但是在最壞情況下它需要指數運行時間，從而使線性規劃問題是否屬于P類一度成為人們關心的問題。后來的橢球算法和投影算法都很好的解決了這個問題。
排序和檢索：
    這兩部分應當是大家比較熟悉的，所謂排序，就是將給定的元素序列按照某種順序關系重新排列成有序序列。例如將n個數組成的序列按照從小到大的順序重新排列；將n個英語單詞組成的的序列按照字典順序重新排列。所謂檢索，就是在給定的集合中查找某個特定的元素或是元素組。排序和檢索已經成為計算機科學技術中最基本、使用最頻繁的算法。下面我們專門談談排序算法（sorting algorithm）。
    在討論此種算法時，數據通常是指由若干記錄組成的文件，每個記錄包含一個或多個數據項，其中能夠標志該記錄的數據項稱為鍵碼。給定一文件的n個記錄{R1,R2,…,Rn}及其相應的鍵碼的集合{K1,K2,…,Kn}。所謂排序算法就是在數據處理中將文件中的記錄按鍵碼的一定次序要求排列起來的算法。若待排序的文件能夠同時裝入計算機的主存中，整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序；若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，有一部分必須放在外存上，則稱此類排序問題為外部排序。當待排序的文件中包含有一些相同鍵碼的記錄時，假如經過排序后這些相同的鍵碼的記錄的相對次序仍然保持不變，則相應的排序算法是穩定的，否則為不穩定的。假如排序算法設計成單處理機完成的，則此排序算法稱為串行（或順序）排序算法；假如排序算法時設計成多處理機實現的，則稱為并行排序算法。
    首先談談內部排序：內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。在排序的過程中，參與排序的記錄序列中存在兩個區域：有序區和無序區。
使有序區中記錄的數目增加一個或幾個的操作稱為一趟排序。
    逐步擴大記錄有序序列長度的方法大致有下列幾類：
一．插入排序
    假設在排序過程中，記錄序列R[1..n]的狀態為：
則一趟直接插入排序的基本思想為：將記錄R
插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變為R[1..i]。
    顯然，完成這個“插入”需分三步進行：
1．查找R的插入位置j+1；
2．將R[j+1..i-1]中的記錄后移一個位置；
3．將R復制到R[j+1]的位置上。
[I]直接插入排序
    利用順序查找實現“在R[1..i-1]中查找R的插入位置”的插入排序。
    注重直接插入排序算法的三個要點：
1．從R[i-1]起向前進行順序查找，監視哨設置在R[0]；
  R[0] = R;    // 設置“哨兵”
  for (j=i-1; R[0].key<R[j].key; --j); // 從后往前找
  return j+1;     // 返回R的插入位置為j+1
2．對于在查找過程中找到的那些要害字不小于R.key的記錄，可以在查找的同時實現向后移動；
  for (j=i-1; R[0].key<R[j].key; --j);  
  R[j+1] = R[j]
3．i = 2，3，…, n, 實現整個序列的排序。
  template<class Elem>
  void InsertionSort ( Elem R[],  int n)
  {
      // 對記錄序列R[1..n]作直接插入排序。
      for ( i=2; i<=n; ++i )
      {
          R[0] = R;            // 復制為監視哨