主方法分析演算法復雜度

㈠ 分析個程序的演算法時間復雜度

最優二叉樹？時間復雜度為：N LogN

㈡ 求下面表達式的時間常數 T(t) = 21 + 0.2*exp(−t/12066 )−1.2*exp(−t/58840 )

難道是用來分析演算法的時間復雜度的？但通用表達式T(n)=3/5T(n-1)+4/5T(n-2)和一般的演算法時間復雜度的遞推式不太一樣，一般的遞推式是將原問題進行分治後的綜合結果，但你這個貌似子問題和原問題的關系更加微妙，所以用代入法、遞歸樹或者主方法貌似都不行，那就用比較傳統的微積分中的差分方程的方法吧：式子等價於差分方程T(n)-3/5T(n-1)-4/5T(n-2)=0，邊界條件T(0)=T(1)=c；其特徵方程是r^2-3/5r+4/5=0，有兩個解r1=(3+√89)/10≈1.24,r2=(3-√89)/10≈-0.64，因此T(n)=C1*r1^n+C2*r2^n，根據邊界條件可得T(0)=C1+C2=c；T(1)=C1*r1+C2*r2=c；解得C1=c(1-r2)/(r1-r2)≈0.87c，C2=c(r1-1)/(r1-r2)≈0.13c那麼T(n)=C1*r1^n+C2*r2^n≈[0.87*1.24^n+0.13*(-0.64)^n]c可以看出，當n很大的時候，(-0.64)^n可以忽略不計，1.24^n起決定性作用，因此該遞歸式所代表的演算法的時間復雜度T(n)是指數級的。

㈢ 編寫一個求一元多項式的值Pn(x0)的演算法，分析演算法的時間復雜度，並在main方法中編寫測試代碼

技術提示：
若n為偶數：
x^n可以轉換為x^(n/2)*x^(n/2)

若n為奇數：
x^n可以轉換為x^(n/2)*x^(n/2)*x
所以單項的時間復雜度為log(n)

(就帶到這了，作業還是自己動手吧:P)

㈣ 主曲線的演算法研究

本程序定義了主曲線和確定主曲線的實際演算法。多邊形線演算法的基本運演算法則是首先確定一條直線段，然後在循環演算法中通過不斷加入新的頂點來增加線段的數量。在加入一個新的頂點以後，所有的頂點位置在一個內部的環中被更新。由演算法所產生的曲線如圖1，在這個例子中，PL運演算法則和HS運演算法則在計算的復雜程度和演算法的完善程度上作出了比較。4段和15段，由在半圓上任意兩個坐標點加入單獨的高斯誤差而產生。
PL演算法[12]在由NIST19號專有資料庫產生的單獨數據元構成的圖像中得到了測試。我們發現PL演算法可以有效的找出沒有環和分叉的圖像的中間軸。這個在圖2中有顯示。由於中間軸可能是一些曲線連接而成而不是只有一條曲線，所以在這里我們擴展了PL演算法，找出數據元的主曲線。擴展了的演算法也包含了實現分段線性骨架的兩個原則，一種獲取字元圖像近似輪廓的初始化方法和一系列用來改善由初始化方法獲得的骨架結構質量的更改結構工作。為了避免混淆，我們用術語「骨架」來表示近似性中間軸的二元圖像，我們把由PL演算法產生出的連接曲線看做模板骨架.
應用
主曲線以前被用在圖像處理領域。這種圖像用來描述在衛星拍攝下的冰川及其輪廓。其主程序用了一個閉合的曲線來估算冰川的輪廓。專家們除去了HS演算法[13]中不合適的部分，並且用更完善的粗略估算冰川輪廓的程序來取代HS演算法的初始化步驟。此外，採用數據元集合，而不是HS演算法所產生的點或線的集合，向中間軸集中的方式來擴展現有的聚合演算法。初始化的曲線由SOM演算法[12]的一個變數產生，在SOM演算法中相互關系被定義為字元圖像的一個最小二叉樹。HS演算法用來使曲線與模板相對應。下一步的要點與SOM演算法的更新規則類似。
利用主曲線實現分段線性骨架的方法被Mahmoud、Datta和Parui[14]等人所提出。同樣的方法，在SOM演算法中用來最優化分段線性骨架的頂點位置。演算法在構建骨架方面採用「自頂向下」的策略：近似性地從一個線性拓撲出發，然後逐步加入環和交叉到骨架中，骨架是由基於SOM演算法的當前幾何樣式得出的。SOM演算法涉及到一個獲取字元圖像分段線性骨架的運演算法則。這種運演算法則以ISODATA演算法[12]為基礎，ISODATA演算法近似於SOM演算法。
目的
主曲線演算法的目的是找出與字元圖像相對應的光滑的分段線性曲線。這些曲線在某個頂點彼此連接，因而在字元圖像的中心平面范圍內形成一個歐幾里德曲線。一個歐幾里德曲線G（V，S）在空間中由變數V和S確定，
主曲線演算法從一個基於傳統稀釋方法的初始化工作開始。初始曲線找出字元圖像的近似拓撲結構，然而,它不是平滑的，而且它通常包含許多假的分叉和不適合的結構元素。為了解決這兩個問題，在前兩步中間增加了更改結構的步驟(圖3)使得主曲線演算法更加有效。在更改結構步驟中，我們運用一些操作手段來調整曲線骨架結構的不完整的地方。(a)圖是在初始化步驟後由主曲線演算法生成的曲線骨架；（b）圖是經過首次擬合-光滑步驟後生成的曲線骨架；(c)圖是經過更改結構後生成的曲線骨架；(d)圖是第二次擬合-光滑步驟後產生的曲線骨架(演算法輸出)。我們重復使用PL演算法的擴展版本來構造光滑的骨架曲線，同時保持曲線與字元圖像的輪廓的距離近似相等。演算法建立在最小能量函數的基礎之上
研究動機與意義
自1904年Spearman[13]提出線性主成分分析方法以來，由於這種方法簡單且便於使用，至今還是數據統計分析的重要工具之一。線性主成分分析的原理是將數據集合投影到一個矢量，使得投影的均方差最大，由此，將這個矢量稱為數據集合的第一主成分。正是這個考慮，在均方差的意義下，這個方法有兩個重要的優點：其一，數據集合可以使用一個矢量來描述，從而達到減小信息描述長度的目的，其二，計算第一以及依次主成分，可以變換為求解基於數據自相關矩陣的特徵值方程。另外，第一與依次主成分矢量保持正交關系，這意味著，與主成分矢量平行的矢量具有與主成分相同的性質。正是這兩個原因，加上在統計上以均方差為保證，主成分分析得到廣泛的應用。 由於信息描述長度與信息保持性之間存在矛盾，相對較長的信息描述長度，較短描述長度的信息描述是以損失信息保持性為代價的，而主成分分析的本質是一種在均方差意義下的統計平均。盡管它可以獲得較短的信息描述長度，但是，信息保持性的代價相當大，由於信息保持性是對數據分布的規律性認識，因此，對某些問題，這個代價可接受的，但是，另外一些問題，可能就不能接受了。例如，對原始語音信號的分析，單純的主成分分析就不一定有效。 為了說明信息描述長度與信息保持性之間的關系，下圖是一個簡單的例子。圖5是由300個包含誤差的數據點構成的餘弦狀分布，圖5(a)的直線是數據的第一主成分線，其對餘弦數據的描述長度顯然較圖5(b)要短，因為這些數據點將使一個線段描述，因此，只需給出線段起點和終點即可，可以認為圖5(a)給出了一個短描述長度的關於數據集合的描述；顯然，圖5(b)對數據的信息保持性則比圖5(a)要好，一方面，它與數據間的距離均方差也要小，另一方面，它勾畫出原始信息的輪廓。圖5(b)恰恰是本文所討論的根據主曲線原理所獲得的結果。那麼，兩種描述哪一個更為合理呢？顯然，這沒有一個一般性的答案，這取決於所需解決問題的需求。
圖5 信息描述長度與信息保持之間的關系
圖5也說明無監督學習較監督學習困難的原因，問題本身的病態定義導致不得不引入復雜性思想，如統計學習理論中的風險結構最小、貝葉斯學派中的貝葉斯信息准則、Kolmogrov演算法[11]復雜度引出的最小描述長度等等，來尋求在信息保持性與數據描述長度之間的折衷。目前，盡管在主曲線的研究中，還存在著大量的數學問題，但是，由於其暗示的廣泛應用前景，已引起計算機科學家的關注，現在應用方面已有大量的報道，如線性對撞機中對電子束運行軌跡的控制、圖像處理中辨識冰原輪廓、手寫體的主曲線模板化、語音識別中對聲音數據的約簡建模和數據可聽化、生態學中尋找種群的有序分布及過程監控。同時，在認知領域Seung[14]提出感知以流形方式存在，並在神經生理學上發現整個神經細胞群的觸發率可以由少量的變數組成的函數來描述，如眼的角度和頭的方向，這隱含了神經元群體活動性是由其內在的低維結構所控制。主曲線本身是流形的一維形式。
原理、發展脈絡以及應用
為了說明主曲線的原理、發展脈絡以及應用，首先介紹其原始動機是必要的。Hastie在他關於主曲線的開創性論文中描述了其研究動機，Hastie認為主曲線與非線性回歸方法的發展上具有對稱性，分別是線性主成分分析與線性回歸分析的非線性推廣模型，Hastie寫到：類似於線性回歸方法的非線性推廣，使用光滑曲線代替線性主成分總結數據，以求出對稱變數之間的曲線，這樣的曲線從數據的中部光滑地通過，且不限制於對數據的光滑線性平均，甚至不限制於數據的中部是直線，只希望使得數據點集合到曲線的正交距離最小。這個陳述清晰地指出了他的研究與主成分分析和回歸分析的區別，並給出了建模的統計目標。同時，從這個陳述中也可以看出，基於直線的主成分分析只是主曲線的一個特例。因此，主曲線的提出，可以理解為基於線性的主成分分析方法向更精確描述實際世界的非線性分析方法的推廣。 應該指出的是，目前，「向非線性」推廣是數據統計分析的研究主流，但是，存在著不同的技術路線。
分類
最典型的研究大致可以分為兩類：
其一，根據統計學習理論中的核技術，將數據集合映射到特徵空間，然後，在特徵空間計算數據集合的主成分，稱為核主成分分析(KPCA)，這個技術路線的本質還是線性主成分分析。
其二，從數據本身的分布出發，希望找到能最好描述數據內在結構的概率分布模型，如生成式拓撲映射(Generative Topographic Mapping,縮寫為GTM)，矢量量化(VQ)及主曲線，以及流形擬合等。提出「主曲線的研究與回歸分析有何區別」是自然的，兩者的動機都是企望求出一個函數代替數據集合，但是，兩者有本質的差別：其一，一般地說，回歸分析是假設數據集合的變數有因果關系，換句話說，數據的變數可以表示為一個因果關系的函數，有些是自變數，有些則是因變數。其二，回歸分析一般需要給定一個數學基函數，回歸分析是根據數據集合中變數的因果關系，計算這個數學基函數待定的參數。這與主曲線的研究動機完全不同。對於前者，主曲線的研究目標是解決數據變數沒有必然因果關系的問題，更重要的是後者，認為事先假定數據服從某種分布(如正態分布)的方法(這與給定數學基函數，根據數據確定參數的方法類似)，對某些未知世界的解釋是不合理的，因為這個假設可能是錯誤的，為了保證數據分析不是假設在一個錯誤結構下，主曲線的研究強調非參數分析。當然，這並不是完全否定了參數法這一經典方法，事實上，參數法在先驗知識明確時存在相當大的好處。總之，根據上述討論的動機，主曲線是尋找一種幾何上直觀、理論上完備、就解決的問題而言，這個方法與主成分分析一致，但是，主曲線的目標不是僅僅尋找一個數據集合的脊樑骨，而是希望獲得數據集合的骨架。數據集合的脊樑骨可以使用線性的方法解決，但骨架就需要藉助非線性方法了。應該強調的是，主曲線繼承了主成分分析的眾多思想，它是主成分分析的非線性推廣。另外，盡管這個方法似乎與回歸分析的目標類似，都是試圖獲得對數據集合信息長度更短的表示，但是，這個方法與回歸分析完全不同，最大的差別是它不是事先給定一個基函數(或假定一個分布)，從而將問題變換為參數估計問題，而是一種非參數的方法

㈤ 如何做演算法研究

一、DSP與TI

為什麼提到電機控制很多人首先會聯想到DSP？而談到DSP控制總繞不過TI，首先DSP晶元是一種具有特殊結構的微處理器。該晶元的內部採用程序和數據分開的哈佛結構，具有專門的硬體乘法器，提供特殊的指令，可以用來快速地實現各種數字信號處理演算法。基於DSP晶元構成的控制系統事實上是一個單片系統，因此整個控制所需的各種功能都可由DSP晶元來實現。因此，可以減小目標系統的體積，減少外部元件的個數，增加系統的可靠性。優點是穩定性好、精度高、處理速度快，目前在變頻器、伺服行業有大量使用。主流的DSP廠家有美國德州儀器（Texas Instruments，TI）、ADI、motorola、傑爾等其他廠商，其中TI的TMS320系列以數字控制和運動控制為主，以價格低廉、簡單易用、功能強大很是受歡迎。

二、常見的電機控制演算法及研究方法

1、電機控制按工作電源種類劃分：可分為直流電機和交流電機。按結構和工作原理可劃分：可分為直流電動機、非同步電動機、同步電動機。不同的電機所採用的驅動方式也是不相同的，這次主要介紹伺服電機，伺服主要靠脈沖來定位，伺服電機接收到1個脈沖，就會旋轉1個脈沖對應的角度，從而實現位移，因此，伺服電機本身具備發出脈沖的功能，所以伺服電機每旋轉一個角度，都會發出對應數量的脈沖，同時又與伺服電機接受的脈沖形成了呼應，或者叫閉環，進而很精確的控制電機的轉動，從而實現精確的定位，可以達到0.001mm。伺服電機相比較普通電機優勢在於控制精度、低頻扭矩，過載能力，響應速度等方面，所以被廣泛使用於機器人，數控機床，注塑，紡織等行業
三、PWM控制及測試結果

脈沖寬度調制是利用微處理器的數字輸出來對模擬電路進行控制的一種非常有效的技術，廣泛應用在從測量、通信到功率控制與變換的許多領域中，脈沖寬度調制是一種模擬控制方式，其根據相應載荷的變化來調制晶體管基極或MOS管柵極的偏置，來實現晶體管或MOS管導通時間的改變，從而實現開關穩壓電源輸出的改變

㈥ 怎麼將C語言遞歸演算法轉化成「遞歸方程」該種演算法時間的復雜度怎麼求有固定的方法嗎

不知道你是怎麼得出"遞歸演算法可以轉化成方程"這個結論的呢? 如果真是這樣,那麼世界上恐怕很多NP問題都可以解決了. 深度優先搜索很多時候就是遞歸結構的,但是並沒有什麼辦法將其轉化成方程解決.

我猜想也許你說的是很特殊的一類遞歸問題,這類遞歸問題可以用數學函數來表達.例如計算階乘的時候,n! = (n-1)*n. 那這個是怎麼的出來的就真沒有固定的套路,但是一般的思想是考慮如何把一個問題轉化成規模更小的幾個問題.

㈦ 遞歸演算法時間復雜度怎麼分析

1、遞歸
是指對一個問題的求解，可以通過同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出復雜形式的解. 遞歸是解決一類問題的重要方法. 遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的. 但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省. 以下討論遞歸的時間效率分析方法，以及與非遞歸設計的時間效率的比較.
2 時間復雜度的概念及其計算方法
演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價准則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程序在計算機中運行的時間來衡量，所花費的時間與演算法的規模n有必然的聯系，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量.
演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重復執行的次數）來估算的，它是問題規模n的某一個函數f(n). 演算法時間度量記作：T（n）=O（f（n））
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間復雜度，簡稱時間復雜度[2].
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程序段中，語句x=x+1的頻度分別為1，n，n2，則這三段程序的時間復雜度分別為O（1），O（n），O（n2）.
求解過程為：先給出問題規模n的函數的表達式，然後給出其時間復雜度T（n）.
但是在現實程序設計過程中，往往遇到的問題都是比較復雜的演算法，就不能很容易地寫出規模n的表達式，也比較難總結其時間復雜度. 遞歸函數就是屬於這種情況. 下面舉例說明遞歸函數的時間復雜度的分析方法.

㈧ 排序演算法的復雜度

由於程序比較簡單，所以沒有加什麼注釋。所有的程序都給出了完整的運行代碼，並在我的VC環境
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平台上應該也不會有什麼
問題的。在代碼的後面給出了運行過程示意，希望對理解有幫助。 這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡： #include<iostream>usingnamespacestd;voidBubbleSort(int*pData,intCount){intiTemp;for(inti=0;i<Count;i++){for(intj=Count-1;j>i;j--){if(pData[j]<pData[j-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[7]={10,9,8,7,6,5,4};BubbleSort(data,7）;for(inti=0;i<7;i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}倒序（最糟情況)
第一輪：10，9，8，7->10，9，7，8->10，7，9，8->7，10，9，8（交換3次)
第二輪：7，10，9，8->7，10，8，9->7，8，10，9（交換2次)
第一輪：7，8，10，9->7，8，9，10（交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8，10，7，9->8，10，7，9->8，7，10，9->7，8，10，9（交換2次)
第二輪：7，8，10，9->7，8，9，10->7，8，10，9（交換1次)
（這是原撰寫人的--7，8，10，9->7，8，10，9->7，8，10，9（交換0次)，第二輪應該是這樣的）
第三輪：7，8，9，10->7，8，9，10（交換1次)
循環次數：6次
交換次數：3次
上面我們給出了程序段，現在我們分析它：這里，影響我們演算法性能的主要部分是循環和交換，
顯然，次數越多，性能就越差。從上面的程序我們可以看出循環的次數是固定的，為1+2+...+n-1。
寫成公式就是1/2*(n-1）*n。
現在注意，我們給出O方法的定義：
若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n)，則f(n) = O(g(n))。（呵呵，不要說沒學好數學呀，對於編程數學是非常重要的！！！）
現在我們來看1/2*(n-1）*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1）*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我們程序循環的復雜度為O(n*n)。
再看交換。從程序後面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換本身同數據源的
有序程度有極大的關系，當數據處於倒序的情況時，交換次數同循環一樣（每次循環判斷都會交換），
復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。亂序時處於中間狀態。正是由於這樣的
原因，我們通常都是通過循環次數來對比演算法。 交換法的程序最清晰簡單，每次用當前的元素一一的同其後的元素比較並交換。 #include<iostream.h>voidExchangeSort(int*pData，intCount){intiTemp;for(inti=0;i<Count-1;i++){//共（count-1）輪，每輪得到一個最小值for(intj=i+1;j<Count;j++){//每次從剩下的數字中尋找最小值，於當前最小值相比，如果小則交換if(pData[j]<pData[i]){iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,sizeof(data)/sizeof(int));for(inti=0;i<sizeof(data)/sizeof(int);i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}第一輪： 9，10，8，7->8，10，9，7->7，10，9，8（交換3次)
第二輪：7，10，9，8->7，9，10，8->7，8，10，9（交換2次)
第一輪：7，8，10，9->7，8，9，10（交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8，10，7，9->8，10，7，9->7，10，8，9->7，10，8，9（交換1次)
第二輪：7，10，8，9->7，8，10，9->7，8，10，9（交換1次)
第一輪：7，8，10，9->7，8，9，10（交換1次)
循環次數：6次
交換次數：3次
從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣
也是1/2*(n-1）*n，所以演算法的復雜度仍然是O(n*n)。由於我們無法給出所有的情況，所以
只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。 現在我們終於可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下）
這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從剩下的部分中
選擇最小的與第二個交換，這樣往復下去。 #include<iostream.h>voidSelectSort(int*pData，intCount){intiTemp;intiPos;for(inti=0;i<Count-1;i++){iTemp=pData[i];iPos=i;for(intj=i+1;j<Count;j++){if(pData[j]<iTemp){iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidmain(){intdata[]={10，9，8，7，6，5，4};SelectSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;cout<< ;}倒序（最糟情況)
第一輪：10，9，8，7->(iTemp=9）10，9，8，7->(iTemp=8）10，9，8，7->(iTemp=7）7，9，8，10（交換1次)
第二輪：7，9，8，10->7，9，8，10(iTemp=8）->(iTemp=8）7，8，9，10（交換1次)
第一輪：7，8，9，10->(iTemp=9）7，8，9，10（交換0次)
循環次數：6次
交換次數：2次
其他：
第一輪：8，10，7，9->(iTemp=8）8，10，7，9->(iTemp=7）8，10，7，9->(iTemp=7）7，10，8，9（交換1次)
第二輪：7，10，8，9->(iTemp=8）7，10，8，9->(iTemp=8）7，8，10，9（交換1次)
第一輪：7，8，10，9->(iTemp=9）7，8，9，10（交換1次)
循環次數：6次
交換次數：3次
遺憾的是演算法需要的循環次數依然是1/2*(n-1）*n。所以演算法復雜度為O(n*n)。
我們來看他的交換。由於每次外層循環只產生一次交換（只有一個最小值）。所以f(n)<=n
所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。 插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然後繼續下一張 #include<iostream.h>voidInsertSort(int*pData，intCount){intiTemp;intiPos;for(inti=1;i<Count;i++){iTemp=pData[i];//保存要插入的數iPos=i-1;//被插入的數組數字個數while((iPos>=0)&&(iTemp<pData[iPos])){//從最後一個（最大數字）開始對比，大於它的數字往後移位pData[iPos+1]=pData[iPos];iPos--;}pData[iPos+1]=iTemp;//插入數字的位置}}voidmain(){intdata[]={10，9，8，7，6，5，4};InsertSort(data，7);for(inti=0;i<7;i++)cout<<data<<;cout<< ;}其他：
第一輪：8，10，7，9->8，10，7，9(交換0次)(循環1次)
第二輪：9，10，8，7->8，9，10，7（交換1次)（循環2次)
第一輪：8，9，10，7->7，8，9，10（交換1次)（循環3次)
循環次數：6次
交換次數：3次
其他：
第一輪：8，10，7，9->8，10，7，9（交換0次)（循環1次)
第二輪：8，10，7，9->7，8，10，9（交換1次)（循環2次)
第一輪：7，8，10，9->7，8，9，10（交換1次)（循環1次)
循環次數：4次
交換次數：2次
上面結尾的行為分析事實上造成了一種假象，讓我們認為這種演算法是簡單演算法中最好的，其實不是，
因為其循環次數雖然並不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<=
1/2*n*(n-1）<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單
排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似
選擇法），但我們每次要進行與內層循環相同次數的『=』操作。正常的一次交換我們需要三次『=』
而這里顯然多了一些，所以我們浪費了時間。
最終，我個人認為，在簡單排序演算法中，選擇法是最好的。 高級排序演算法中我們將只介紹這一種，同時也是目前我所知道（我看過的資料中）的最快的。
它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數組中間值，然後
把比它小的放在左邊，大的放在右邊（具體的實現是從兩邊找，找到一對後交換）。然後對兩邊分別使
用這個過程（最容易的方法——遞歸）。
1.快速排序：//這段代碼編譯可以通過，一運行就出錯，內部的細節有些問題，我還沒找到解決方法。 #include<iostream.h>voidrun(int*pData，intleft，intright){inti，j;intmiddle，iTemp;i=left;j=right;middle=pData[left];do{while((pData[i]<middle)&&(i<right))//從左掃描大於中值的數i++；while((pData[j]>middle)&&(j>left))//從右掃描大於中值的數j--;if(i<=j)//找到了一對值{//交換iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;i++;j--;}}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）//當左邊部分有值（left<j)，遞歸左半邊if(left<j)run(pData，left，j);//當右邊部分有值（right>i)，遞歸右半邊if(right>i)run(pData，i，right);}voidQuickSort(int*pData，intCount){run(pData，0，Count-1）;}voidmain(){intdata[]={10，9，8，7，6，5，4};QuickSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;//原作者此處代碼有誤，輸出因為date[i],date數組名輸出的是地址cout<< ;}這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析演算法：首先我們考慮最理想的情況
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。
第一層遞歸，循環n次，第二層循環2*(n/2）......
所以共有n+2(n/2）+4(n/4）+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以演算法復雜度為O(log2(n)*n)
其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那麼他將變
成交換法（由於使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全
不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。
如果你擔心這個問題，你可以使用堆排序，這是一種不穩定的O(log2(n)*n)演算法，但是通常情況下速度要慢
於快速排序（因為要重組堆）。 雙向冒泡
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。 #include<iostream.h>inlinevoidexchange(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}voidbubblesort(int*array,intnum){inti,j,k,flag=0;for(i=0;i<num;i++){printf(%d,array[i]);}printf( );for(i=0;i<num;i++){//所有數的個數為num個flag=0;for(j=i;j<num-i-1;j++){//每循環一次最底端的數的順序都會排好，所以初始時j=i;if(array[j]>array[j+1]){exchange(&array[j],&array[j+1]);flag=1;}}for(k=num-1-i-1;k>i;k--){//每循環一次最頂端的數據的順序也會排好，所以初始時k=num-i-2if(array[k]<array[k-1]){exchange(&array[k],&array[k-1]);flag=1;}}if(flag==0){//如果flag未發生改變則說明未發生數據交換，則排序完成return;}}}voidmain(){intdata[]={10，9，8，7，6，5，4，3，2，1，-10，-1};bubblesort(data，12）;for(inti=0;i<12;i++)cout<<data<<;cout<< ;} 這個程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//這里重載了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index，char* strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include MyData.h
template <class T>
void run(T* pData，int left，int right)
{
int i，j;
T middle，iTemp;
i = left;
j = right;
//下面的比較都調用我們重載的操作符函數
middle = pData[(left+right)/2]; //求中間值
do{
while((pData<middle) && (i<right))//從左掃描大於中值的數
i++；
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值（left<j)，遞歸左半邊
if(left<j)
run(pData，left，j);
//當右邊部分有值（right>i)，遞歸右半邊
if(right>i)
run(pData，i，right);
}
template <class T>
void QuickSort(T* pData，int Count)
{
run(pData，0，Count-1）;
}
void main()
{
CMyData data[] = {
CMyData（8，xulion)，
CMyData（7，sanzoo)，
CMyData（6，wangjun)，
CMyData（5，VCKBASE)，
CMyData（4，jacky2000)，
CMyData（3，cwally)，
CMyData（2，VCUSER)，
CMyData（1，isdong)
};
QuickSort(data，8）;
for (int i=0;i<8;i++)
cout<<data.m_iIndex<< <<data.GetData()<< ;
cout<< ;

㈨ 數據結構和演算法方面的問題。關於時間復雜度的求法。關於代入法和主定理，謝謝！ 問題可能有點多，

在我看來主定理並沒什麼大的用處, 不僅條件需要仔細驗證, 而且三種情況之間還有真空地帶, 還不如掌握些常用的解遞推的方法更實用.

當然, 從你的敘述來看, 你連主定理都沒有理解, 所以你的首要任務是先學會用主定理.

粗略地講, 主定理的基本思想是對
T(n)=aT(n/b)+f(n)
型的遞推, 到底是 aT(n/b) 這項大還是 f(n) 這項大, 所以引出分水嶺 g(n)=n^{ln b/ln a}.

對於第三題, 取 ε=ln6/ln5-1>0, 那麼 f(n)=n^1=n^{ln6/ln5-ε}, 比 g(n) 低 n^ε, 然後代主定理就得到 T(n)=Θ(n^{ln6/ln5})

對於第二題, f(n)=nln n, g(n)=n, 兩者間沒有多項式的鴻溝, 就不能直接用主定理. 這也就是我說主定理其實沒啥大用的道理.

一般來講掌握下面的方法就可以解決這一大類遞推, 其實主定理也是這樣推出來的.

對於第二題, 只考慮 n=2^k 的子列, 換元之後把 T(2^k) 記成 S(k), 那麼
S(k) = 2S(k-1) + 2^k * k
S(k-1) = 2S(k-1) + 2^{k-1} * (k-1)
...
S(1) = 2S(0) + 2
把左端為 S(k-j) 的式子乘上 2^j 之後全加起來就消去了所有中間項得到
S(k) = 2^k S(0) + 2^k[k+(k-1)+...+1] = 2^k*O(1) + 2^k*Θ(k^2) = Θ(2^k*k^2)
寫成 T(n) 的形式就是 T(n)=Θ(n*(ln n)^2)
由於 T(n) 是單調的, 考慮上述子列足夠推出漸進量級了

對於第三題, 同樣的方法, 令 n=5^k, S(k) = T(5^k), 那麼
S(k) = 6S(k-1) + 5^k
S(k-1) = 6S(k-2) + 5^{k-1}
...
S(1) = 6S(0) + 5
把左端為 S(k-j) 的式子乘上 6^j 之後全加起來就消去了所有中間項得到
S(k) = 6^k S(0) + [5^k + 6*5^{k-1} + ... + 6^{k-1}*5]
= 6^k*Θ(1) + 5*Θ(6^k) = Θ(6^k)
注意後面那堆求和是等比數列求和
換回去就得到 T(n) = Θ(n^{ln6/ln5})

一般方法大致就是這樣, 當然你得會選擇合適的變數代換, 也得掌握一些基本的求和, 有時候求和不易求可以用積分來代替, 不影響漸進量級

㈩ C++中排序的演算法分析(文字分析)

排序演算法是一種基本並且常用的演算法。由於實際工作中處理的數量巨大，所以排序演算法對演算法本身的速度要求很高。
而一般我們所謂的演算法的性能主要是指演算法的復雜度，一般用O方法來表示。在後面我將給出詳細的說明。
對於排序的演算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。
我將按照演算法的復雜度，從簡單到難來分析演算法。
第一部分是簡單排序演算法，後面你將看到他們的共同點是演算法復雜度為O(N*N)（因為沒有使用word,所以無法打出上標和下標）。
第二部分是高級排序演算法，復雜度為O(Log2(N))。這里我們只介紹一種演算法。另外還有幾種演算法因為涉及樹與堆的概念，所以這里不於討論。
第三部分類似動腦筋。這里的兩種演算法並不是最好的（甚至有最慢的），但是演算法本身比較奇特，值得參考（編程的角度）。同時也可以讓我們從另外的角度來認識這個問題。
第四部分是我送給大家的一個餐後的甜點——一個基於模板的通用快速排序。由於是模板函數可以對任何數據類型排序（抱歉，裡面使用了一些論壇專家的呢稱）。

現在，讓我們開始吧：

一、簡單排序演算法
由於程序比較簡單，所以沒有加什麼注釋。所有的程序都給出了完整的運行代碼，並在我的VC環境
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平台上應該也不會有什麼
問題的。在代碼的後面給出了運行過程示意，希望對理解有幫助。
1.冒泡法：
這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)
第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
上面我們給出了程序段，現在我們分析它：這里，影響我們演算法性能的主要部分是循環和交換，
顯然，次數越多，性能就越差。從上面的程序我們可以看出循環的次數是固定的，為1+2+...+n-1。
寫成公式就是1/2*(n-1)*n。
現在注意，我們給出O方法的定義：
若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n) = O(g(n))。（呵呵，不要說沒
學好數學呀，對於編程數學是非常重要的！！！）
現在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我們程序循環的復雜度為O(n*n)。
再看交換。從程序後面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換本身同數據源的有序程度有極大的關系，當數據處於倒序的情況時，交換次數同循環一樣（每次循環判斷都會交換），復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。亂序時處於中間狀態。正是由於這樣的原因，我們通常都是通過循環次數來對比演算法。

2.交換法：
交換法的程序最清晰簡單，每次用當前的元素一一的同其後的元素比較並交換。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,9,10,8->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交換1次)
第二輪：7,10,8,9->7,8,10,9->7,8,10,9(交換1次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣也是1/2*(n-1)*n，所以演算法的復雜度仍然是O(n*n)。由於我們無法給出所有的情況，所以只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。
3.選擇法：
現在我們終於可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下）這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從省下的部分中選擇最小的與第二個交換，這樣往復下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次)
第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)
第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次)
循環次數：6次
交換次數：2次
其他：
第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1次)
第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次)
第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
遺憾的是演算法需要的循環次數依然是1/2*(n-1)*n。所以演算法復雜度為O(n*n)。
我們來看他的交換。由於每次外層循環只產生一次交換（只有一個最小值）。所以f(n)<=n
所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。

4.插入法：
插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然後繼續下一張
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7(交換1次)(循環1次)
第二輪：9,10,8,7->8,9,10,7(交換1次)(循環2次)
第一輪：8,9,10,7->7,8,9,10(交換1次)(循環3次)
循環次數：6次
交換次數：3次
其他：
第一輪：8,10,7,9->8,10,7,9(交換0次)(循環1次)
第二輪：8,10,7,9->7,8,10,9(交換1次)(循環2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)(循環1次)
循環次數：4次
交換次數：2次
上面結尾的行為分析事實上造成了一種假象，讓我們認為這種演算法是簡單演算法中最好的，其實不是，
因為其循環次數雖然並不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單
排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似
選擇法），但我們每次要進行與內層循環相同次數的『=』操作。正常的一次交換我們需要三次『=』
而這里顯然多了一些，所以我們浪費了時間。
最終，我個人認為，在簡單排序演算法中，選擇法是最好的。

二、高級排序演算法：
高級排序演算法中我們將只介紹這一種，同時也是目前我所知道（我看過的資料中）的最快的。
它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數組中間值，然後
把比它小的放在左邊，大的放在右邊（具體的實現是從兩邊找，找到一對後交換）。然後對兩邊分別使
用這個過程（最容易的方法——遞歸）。
1.快速排序：
#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中間值
do{
while((pData[i]<middle) && (i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left<j)
run(pData,left,j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析演算法：首先我們考慮最理想的情況
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。
第一層遞歸，循環n次，第二層循環2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以演算法復雜度為O(log2(n)*n)
其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那麼他將變
成交換法（由於使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全
不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。
如果你擔心這個問題，你可以使用堆排序，這是一種穩定的O(log2(n)*n)演算法，但是通常情況下速度要慢於快速排序（因為要重組堆）。
三、其他排序
1.雙向冒泡：
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。
代碼看起來復雜，仔細理一下就明白了，是一個來回震盪的方式。
寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換（我不這么認為，也許我錯了）。
反正我認為這是一段有趣的代碼，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
2.SHELL排序
這個排序非常復雜，看了程序就知道了。
首先需要一個遞減的步長，這里我們使用的是9、5、3、1（最後的步長必須是1）。
工作原理是首先對相隔9-1個元素的所有內容排序，然後再使用同樣的方法對相隔5-1個元素的排序
以次類推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step個元素的下標
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使用0
步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。
這個演算法的得名是因為其發明者的名字D.L.SHELL。依照參考資料上的說法：「由於復雜的數學原因
避免使用2的冪次步長，它能降低演算法效率。」另外演算法的復雜度為n的1.2次冪。同樣因為非常復雜並
「超出本書討論范圍」的原因（我也不知道過程），我們只有結果了。

四、基於模板的通用排序：
這個程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index,char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//這里重載了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"
template <class T>
void run(T* pData,int left,int right)
{
int i,j;
T middle,iTemp;
i = left;
j = right;
//下面的比較都調用我們重載的操作符函數
middle = pData[(left+right)/2]; //求中間值
do{
while((pData[i]<middle) && (i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left<j)
run(pData,left,j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right>i)
run(pData,i,right);
}
template <class T>
void QuickSort(T* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
CMyData data[] = {
CMyData(8,"xulion"),
CMyData(7,"sanzoo"),
CMyData(6,"wangjun"),
CMyData(5,"VCKBASE"),
CMyData(4,"jacky2000"),
CMyData(3,"cwally"),
CMyData(2,"VCUSER"),
CMyData(1,"isdong")
};
QuickSort(data,8);
for (int i=0;i<8;i++)
cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
cout<<"\n";
}