1.冒泡法：

這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡:

Sinclude<iostream.h>

voidBubbleSort(int*pData,intCount)

(

intiTemp;

for(inti=l;i<Count;i++)

{

for(intj=Count-l;j>=i;j一)

(

if(pData[j]<pData[j-l])

(

iTemp=pData[j-1];

pData[j-l]=pData[j];

pData[j]=iTemp;

)

)

}

)

voidmain0

(

intdata[]={10,9,8,7,6,5,4};

BubbleSort(data,7);

for(inti=0;i<7;i++)

cout<<data[i]?z/"\

cout<<"\n";

)

圖示:before_compare|one_turn|two_turn|three_turnfour_turn|five_turn|six_turn

1010101010104

999994108

888499777

488866477

775466666

4555555通過上圖可以看出，冒

泡法形象的描述來，4這個元素就像一個氣泡逐漸冒到上面來了。我們排序的有7個元素,

最壞的情況全部倒序，4這個元素要冒上來需要6次。因此，n個元素，最壞的情況，需要

移動：1+2+3+...+（n-l）=l/2*n（n-l）次。倒序（最糟情況）

第一輪：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-lo寫成公式就是l/2*(n-l)*n。現在注意，我們給出0方法的定義：

若存在一常量K和起點n0,使當n>=n0時，有f(n)<=K*g(n),則f(n)=O(g(n))?(呵

呵，不要說沒學好數學呀，對于編程數學是非常重要的！！！)

現在我們來看1/2*(n-l)*n,當K=l/2,n0=l,g(n)=n*n時,l/2*(nT)*n〈=l/2*n*n=K*g(n)。

所以f(n)=O(g(n))=O(n*n)。所以我們程序循環的復雜度為0(n*n)。

再看交換。從程序后面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換

本身同數據源的有序程度有極大的關系，當數據處于倒序的情況時,交換次數同循環一樣(每

次循環判斷都會交換)，復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為0(0)。

亂序時處于中間狀態。正是由于這樣的原因，我們通常都是通過循環次數來對比算法。2.

交換法：

交換法的程序最清晰簡單，每次用當前的元素一一的同其后的元素比較并交換。

#include〈iostream.h>

voidExchangeSort(int*pData,intCount)

(

intiTemp;

for(inti=0;i<Count-l;i++)

(

for(intj=i+l;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,7);

for(inti=0;i<7;i++)

cout?data[i]?w

cout?"\n";

}beforecompareIoneturntwoturn|threeturnfourturn|fiveturn|sixturn

10987654

91010101010108

89999977

78888666

677755555

664444445從上

面的算法來看，基本和冒泡法的效率一樣。

倒序（最糟情況）

第一輪: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次

從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣也是

l/2*（nT）*n,所以算法的復雜度仍然是0（n*n）。由于我們無法給出所有的情況，所以只能

直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。

3.選擇法：

現在我們終于可以看到點希望：選擇法，這種方法提高了一點性能（某些情況下）這種方

法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從省下的部分中選擇

最小的與第二個交換，這樣往復下去。

^include<iostream.h>

voidSelectSort（int*pData,intCount）

（

intiTemp;

intiPos;

for（inti=0;i<Count-l;i++）

（

iTemp=pData[i];

iPos=i;

for（intj=i+l;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<〈〃\n〃；

}該排序法的圖示如下；i=0時：iTemp=pData[0]=10；iPos=i=0；

j=l；

pData[j]<iTemp—>pData[l]=9<10;

iTemp=pData[1]=9;

ipos=j=l;

j++=2

j=2;

pData[j]<iTemp---->pData[2]=8<9;

iTemp=pData[2]=8;

ipos=j=2;

j++=3

j=6;

pData[j]<iTemp---->pData[6]=4<5;

iTemp=pData[6]=4;

ipos=j=6;

j++=7;

pData[6]=Pdata[0];

pData[0]=4;

before_compareoneturntwoturnthreeturn

10444

9955

8886

7777

6668

5599

4101010由上面可以看到選擇排序法并沒有在一開始就交換數據，而

是用第一個數據去和所有的數據比較，如果第一個數據小于第二個數據，那么，先把第二個

數據放到個臨時變量里面，同時記錄這個較小的數據在待排序的集合中的位置。再用該集

合中的下一個數據和我們之前放在臨時變量中的數據比較。也就是我們目前認為最小的數據

比較，如果比我們之前選出來的數據小，那么再替換該變量。如果比這個數據大，則繼續用

下一個數據來比較。知道所有的數據都比較完為止。到這時，臨時變量里面訪的就是最小的

數據了。我們把這個數據和第-個數據做對換。此時，最小的元素排到了第一位。倒序(最

糟情況)

第一輪：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次

遺憾的是算法需要的循環次數依然是l/2*(n-l)*n。所以算法復雜度為0(n*n)。

我們來看他的交換。由于每次外層循環只產生一次交換(只有一個最小值)。所以f(n)<=n

所以我們有f(n)=0(n)。所以，在數據較亂的時候，可以減少一定的交換次數。4.插入法：

插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然后繼

續下一張

#include<iostream.h>

voidInsertSort(int*pData,intCount)

(

intiTemp;

intiPos;

for(inti=l;i<Count;i++)

(

iTemp=pData[i];

iPos=i-1;

while((iPos>=0)&&(iTemp<pData[iPos]))

(

pData[iPos+l]=pData[iPos];

iPos一;

}

pData[iPos+l]=iTemp;

}

voidmainO

(

intdata[]={10,9,8,7,6,5,4};

InsertSort(data,7);

for(inti=0;i<7;i++)

cout<<data[i]?/z

cout??z\n，z;

)

i=l時：

iTemp=pData[l]=9

ipos=l-l=0;

ipos=0>=0&&iTemp=9<pData[0]=10;

pData[1]=pData[0]=10;

ipos-=0-l=-l;

pData[0]=9;9-10-8-7-6-5-4

i=2時：

iTemp=pData[2]=8

ipos=2-l=l;

ipos=l>=0&&iTemp=8<pData[1]=10;

pData[2]=pData[l]=10;

ipos―=1-1=0;9-10-10-7-6-5-4

ipos=0〉=0&&iTemp=8<pData[0]=9;

pData[1]=pData[0]=9;

ipos-=0-l=-l;

pData[0]=8;8-9-10-7-6-5-4

i=3時：

iTemp=pData[3]=7

ipos=3-l=2;

ipos=2>=0&&iTemp=7<pData[2]=10;

pData[3]=pData[2]=10;

ipos―=2-1=1;8-9-10-10-6-5-4

ipos=l>=0&&iTemp=8<pData[1]=9;

pData[2]=pData[1]=9;

ipos—=1-1=0;8-9-9-10-6-5-4

iposz:0>=0&&iTemp=7<pData[0]=8;

pData[1]=pData[0]=8;

ipos-=0-1=-l;

pData[0]=7;7-8-9-10-6-5-4i=4時:

iTemp=pData[4]=6;

ipos=4-l=3;

ipos=3>=0&&iTemp=6<pData[3]=10;

pData[4]=pData[3]=10;

ipos-=3-1=2;7-8-9-10-10-5-4

ipos=2>=0&&iTemp=7<pData[2]=9;

pData[3]=pData[2]=9;

ipos-=2-1=1;7-8-9-9-10-5-4

ipos=l>=0&&iTemp=7<pData[1]=8;

pData[2]=pData[1]=8;

ipos―=1-1=0;7-8-8-9-10-5-4

ipos=0>=0&&iTemp=7<pData[0]=7;

pData[1]=pData[0]=7;

ipos-=1-1=0;

pDate[0]=6;6-7-8-9-10-5-4

由上述可知：插入排序是先把集合中的下一個元素抽取出來

放到一個臨時變量里面和第一個元素比較。并記錄該元素在集合中的位置

如果第二個元素比第一個小，那么第一個元素和第二個元素對調。下一次

再用第三個元素先和變化后的第二個元素比較，如果變化后的第二個元素

小于第三個元素，用第二個元素的值覆蓋第三個元素。在從臨時變量里面

取出該元素放到第二個元素中去。

倒序（最糟情況）

第一輪：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,二,9（交換1次）（循環2次）

第一輪：7,8,10,9->7,8,9,10（交換1次）（循環1次）

循環次數：4次

交換次數：2次

上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中最好的，其

實不是，因為其循環次數雖然并不固定，我們仍可以使用0方法。從上面的結果可以看出，

循環的次數f（n）<=l/2*n*（n-l）<=l/2*n*n。所以其復雜度仍為0（n*n）（這里說明一下,其

實如果不是為了展示這些簡單排序的不同，交換次數仍然可以這樣推導）。現在看交換，從

外觀上看，交換次數是0（n）（推導類似選擇法），但我們每次要進行與內層循環相同次數的

操作。正常的一次交換我們需要三次而這里顯然多了一些，所以我們浪費了時間。

最終，我個人認為，在簡單排序算法中，選擇法是最好的。插入排序

#include<iostream>

usingnamespacestd;

voidcoutstream(inta[],intn){

for(inti=0;i!=n;i++)

)

voidinsertsort(inta[],intn){

inttemp;

for(inti=l;i<n;i++)

(

intj=i;

temp=a[i];〃先把a[i]位置的數據存起來

while(j>O&&temp<a[j-l])

(

a[j]=a[j-l];

J—；

)

a[j]=temp;

)

)

intmain()

(

inta[5]={l,6,4,8,4);

insertsort(a,5);〃插入排序

coutstream(a,5);//

return0;

)

二、高級排序算法：

高級排序算法中我們將只介紹這一種，同時也是目前我所知道(我看過的資料中)的最快的。

它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數組

中間值，然后把比它小的放在左邊，大的放在右邊(具體的實現是從兩邊找，找到一對后交

換)。然后對兩邊分別使用這個過程(最容易的方法一遞歸)。

1.快速排序：

#include<iostream.h>

voidrun(int*pData,intleft,intright)

inti,j;

intmiddle,iTemp;

i=left;

J=right;

middle=pData[(left+right)/2];〃求中間值

do{

whi1e((pData[i]<midd1e)&&(i<right))〃從左掃描大于中值的數

i++；

while((pData[j]>middle)&&(j>left))〃從右掃描大于中值的數

j—；

if(iCj)〃找到了一對值

(

〃交換

iTemp=pData[i];

pData[i]=pDataEj];

pData[j]=iTemp;

i++；

j—；

)

}while(i〈=j);〃如果兩邊掃描的下標交錯，就停止(完成一次)

〃當左邊部分有值(left〈j),遞歸左半邊

if(left<j)

run(pData,left,j);

〃當右邊部分有值(right"),遞歸右半邊

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]?/z

cout?，z\n，z;

}

這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想

的情況

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

所以算法復雜度為0(log2(n)*n)

其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，

那么他將變成交換法(由于使用了遞歸，情況更糟)。但是你認為這種情況發生的幾率有多

大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。

如果你擔心這個問題，你可以使用堆排序，這是種穩定的0(log2(n)*n)算法，但是通常

情況下速度要慢于快速排序(因為要重組堆)。三、其他排序

1.雙向冒泡：

通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。

代碼看起來復雜，仔細理一下就明白了，是一個來回震蕩的方式。

寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換(我不這么認為，也許我錯

了)。

反正我認為這是一段有趣的代碼，值得一看。

^include<iostream.h>

voidBubble2Sort(int*pData,intCount)

intiTemp;

intleft=1;

intright=Count-1;

intt;

do

(

〃正向的部分

for(inti=right;i>=left;i--)

(

if(pData[i]<pData[i-1])

(

iTemp=pData[i];

pData[i]=pData[i-l];

pData[i-l]=iTemp;

t=i;

)

)

left=t+1;

〃反向的部分

for(i=left;i<right+l;i++)

if(pData[i]<pData[i-1])

iTemp=pData[i];

pData[i]=pData[i-l];

pData[i~l]=iTemp;

t=i;

)

)

right=t-1;

}while(left<=right);

)

voidmain()

(

intdata[]={10,9,8,7,6,5,4};

Bubble2Sort(data,7);

for(inti=0;i<7;i++)

cout<<data[i]?/z;

cout?"\n〃；

}快速排序

#include<iostream>

usingnamespacestd;

classQuicksort

(

public:

voidquick_sort(int*x,intlow,inthigh)

(

intpivotkey;

if(low<high)

(

pivotkey=partion(x,low,high);

quick_sort(x,low,pivotkey-1);

quick_sort(x,pivotkey+1,high);

)

)

intpartion(int*x,intlow,inthigh)

(

intpivotkey;

pivotkey=x[low];

while(low<high)

(

whi1e(low<high&&x[high]>=pivotkey)

—high;〃還有while循環只執行這一句

x[low]=x[high];

while(low<high&&x[low]<=pivotkey)

++low;〃還有while循環只執行這一句

x[high]=x[low];

)

x[low]=pivotkey;

returnlow;

)

)；

intmain()

(

intx[10]={52,49,80,36,14,58,61,97,23,65};

Quicksortqs;

qs.quicksort(x,0,9);

cout<<〃排好序的數字序列為：〃“endl;

for(inti=0;i<10;i++)

(

printf('%d",x[i]);

)

return0;

)

2.SHELL排序

這個排序非常復雜，看了程序就知道了。

首先需要一個遞減的步長，這里我們使用的是9、5、3、1(最后的步長必須是1)。

工作原理是首先對相隔9-1個元素的所有內容排序,然后再使用同樣的方法對相隔5-1個元

素的排序以次類推。

#include<iostream.h>

voidShellSort(int*pData,intCount)

(

intstep[4];

step[0]=9;

step[l]=5;

step[2]=3;

step[3]=1;

intiTemp;

intk,s,w;

for(inti=0;i<4;i++)

(

k=step[i];

s=-k;

for(intj=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;

}

)

}

voidmain()

(

intdata[]={10,9,8,7,6,5,4,3,2,1,-10,-1};

ShellSort(data,12);

for(inti=0;i<12;i++)

cout<<data[i]?z,

cout〈<“\n〃；

)

呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免

使用0步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。這個算法的得名是因為

其發明者的名字D.L.SHELL。依照參考資料上的說法：”由于復雜的數學原因避免使用2的

基次步長，它能降低算法效率」另外算法的復雜度為n的1.2次暴。同樣因為非常復雜并

“超出本書討論范圍”的原因(我也不知道過程)，我們只有結果了

#include<iostream>

usingnamespacestd;

voidmaopao(int*list,intn)

(

inti=n,j,temp;

boolexchange;〃當數據已經排好時，退出循環

for(i=0;i<n;i++)

(

exchange=false;

for(j=0;j<n-i-l;j++)

(

if(list[j]>list[j+U)

(

temp=list[j];

list[j]=list[j+l];

list[j+l]=temp;

exchange=true;

)

if(!exchange)

(

return;

}

}

}

intmain()

(

inta[7]={32,43,22,52,2,10,30);

maopao(a,7);

for(inti=0;i<7;i++)

cout?a[i]?z/

return0;

)

shell排序的思想是根據步長由長到短分組，進行排序，直到步長為1為止，屬于插入排序

的一種。下面用個例子更好的理解一下無序數列：32,43,56,99,34,8,54,761.

首先設定gap=n/2=4于是分組32,34排序32,3443,88,4356,

5454,5699,7676,99數列變成32,8,54,76,34,43,56,

992.gap=gap/2=2于是分組32,54,34,56排序32,34,54,568,76,43,99

8,43,76,99于是數列變成32,8,34,43,54,76,56,993.gap=gap/2=l于是分組32,

8,34,43,54,76,56,99排序8,32,34,43,54,56,76,99gap=l結束……相應

的C語言代碼引用K&RC程序設計一書中給出的代碼voidshellsort(intv[],intn)

{intgap,i,j,temp;for(gap=n/2;gap〉0;gap/=2)//設定步長for(i=gap;i<n;++i)

〃在元素間移動為止for(j=i-gap;j>=O&&v[j]>v[j+gap];j-=gap){〃比較相距

gap的元素，逆序互換temp=v[j];v[j]=v[j+gap];

v[j+gap]=temp;}}〃帕斯卡恒等式為C(n,k)=C(nT,kT)+C(nT,k)

longfun(longn,longr)

(

if(r<0||n<0)

(

printf('\nError.Exit!”);

exit(1);

}

if(r>n)return0;

if(r==l||r==nT)〃根據組合定義，我們有C(n,l)=C(n,n-l)=n

returnn;

if(r==0||r==n)〃根據組合定義，我們有C(n,0)=C(n,n)=l

return1;

returnfun(n-1,r)+fun(n-1,rT);〃帕斯卡組合公式

}

〃選擇法對數組排序的函數模板

template<classT>

voidselectsort(Tarr[],intsize)

(

Ttemp;

inti,j;

for(i=0;i<size-l;i++)

for(j=i+l;j<size;j++)

if(arr[i]>arr[jj)

(

temp二arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

)

//冒泡法對數組排序的函數模板

template<classT>

voidbubblesort(T*d,intn)

(

inti,j;

Tt;

for(1=0;i<n-l;i++)

for(j=0;j<n-i-l;j++)

if(d[j]>d[j+l])

{

t=d[j];

d[j]=d[j+l];

d[j+l]=t;

)

)

〃插入法對數組排序的函數模板

template<classT>

voidInsertSort(TA[],intn)

(

inti,j;

Ttemp;

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

temp=A[i];

for(j=i-l;j>=0&&temp<A[j];j—)

A[j+l]=A[j];

A[j+1]=temp;

)

}

〃二分查找法的函數模板

template<classT>

intbinary_search(Tarray[],Tvalue,intsize)

(

inthigh=size-1,low=0,mid;

while(low<=high)

(

mid=(high+low)/2;

if(value<array[mid])

high=mid-1;

elseif(value>array[mid])

low=mid+1;

elsereturnmid;

)

return-1;

)

將2、36進制數與10進制數相互轉換

〃將2~36進制數轉換成10進制數

unsignedintOthToDec(char*oth,intbase)〃base為已知數的進制

(

unsignedinti=0,dec=0;

while(oth[i])

(

dec*二base;

if(oth[i]>=0，&&oth[i"二'9')

dec+=oth[i]&15;//dec+=oth[i]-48;

elseif(oth[i]>='A'&&oth[i]<=，T)

dec+=oth[i]~55;

elseif(oth[i]>=，a，&&oth[i]<=，z)

dec+=oth[i]-87;

i++；

)

returndec;

)

〃將10進制(無符號)轉2?36進制數

char*DecToOth(char*oth,unsignedintdec,intbase)//base為要轉換的數的進

制

charch,*left=oth,*right=oth,num[]=，/0123456789ABCDEFGHIJKLMN0PQRSTUVWXYZ//;

do

{

*right=num[dec%base];

right++;

}while(dec/=base);

*right=，\0，;

right—;

while(left<right)

(

ch=*left;

*left=*right;

*right=ch;

left++;right一；

)

returnoth;

)

〃統計substr在str中的個數

intfun(char*str,char*substr)

(

intn=0;

char*q;

q=substr;

while(*str!=，\0J)

(

if(*str二二*substr)

(

str++;

substr++;

if(*substr==，\0')

{

n++;

substr=q;

)

)

else

(

str++;substr=q;

)

returnn;

}使用數組實現約瑟夫環：

ttinclude<stdio.h>

#include<stdlib.h>

main()

(

intm,n,i=l,j,k=l,per,o;

printf(〃請輸入總共的人數，記為n\n〃);

scanf(〃/d〃，&n);

intarray[n+1];

intorder[n+1];

printf("請輸入幾號出圈，記為m\n〃)；

scanf("%d〃，&m);

printf(〃\n**************************************\n〃);

for(;i<n;i++)〃數組鏈表模擬

array[i]=i+l;

array[n]=l;

printf(〃%d〃,array[n]);

i=l;j=l;per=n;

while(array[i]!=i){

if(k==m){

order[j]=i;

j++；

array[per]=array[i];

k=0;

for(o=l;o<=j;o++)

printf("%d*”,order[o]);

)

else{printf(，z%d”,array[i]);

per=i;

i二array[i];

k++;

)

}

order[n]=i;

printf(〃\n**************************************\n");

for(i=l;i<=n;i++)

printf(〃%d〃，order[i]);

system(/zpause，z);

return0;

}輸入正整數N,然后是N*N個正整數，表示邊權鄰接矩陣。

輸出求解過程。

/*

Problem:WeightedBipartiteMatching

Algorithm:HungarianAlgorithm

Reference:DouglasB.West,IntroductiontoGraphTheory,125-129

Author:PC

Date:2005.2.23

*/

#include<iostream.h>

#include<iomanip.h>

#include<fstream.h>

#include〈memory.h>

ifstrearnfin("input.txt〃)；

#definecinfin

constintmax二50;

boolT[max],R[max],visited[max];

intU[max],V[max],gt[max][max],x[max],y[max];

intN;

voidoutput()

(

inti,j;

for(i=0;i<N;i++)

(

for(j=0;j<N;j++)

(

cout?setw(2)?gt[i][j]?，';

}

if(R[i])cout?setw(2)?，Rf?);

cout?endl;

)

for(i=0;i<N;i++)

if(T[i])cout?setw(2)?，V?J';

elsecout?setw(2)'；

cout<<endl;

)

intpath(intu)

intv;

for(v=0;v<N;v++)

if(gt[u][v]==0&&!visited[v])

(

visited[v]=l;

if(y[v]<0"path(y[v]))

(

x[u]=v;y[v]=u;

R[u]=l;T[v]=0;

return1;

}else{

T[v]=l;

R[y[v]]=0;

}

)

)

return0;

intmain0

(

for(;cin?N;){

inti,j,ans,sigma,step=0;

for(i=0;i<N;i++)

(

U[i]=V[i]=0;

for(j=0;j<N;j++)

(

cin?gt[i][j];

if(U[i]<gt[i][j])U[i]=gt[i][j];

)

}

for(i=0;i<N;i++)

(

for(j=0;j<N;j++)

(

gt[i][j]=U[i]-gt[i][j];

}

}

//////////////////////////////////////////////////////////

for(;;)

ans=O;

sigma=O;

memset(x,-1,sizeof(x));

memset(y,-1,sizeof(y));

memset(R,0,sizeof(R));

memset(T,0,sizeof(T));

for(i=0;i<N;i++)

(

if(x[i]<0)

(

memset(visited,0,sizeof(visited));

ans+=path(i);

)

for(j=0;j<N;j++)

(

if(sigma<l|Isigma>gt[i][j]&>[i][j]>0)

sigma=gt[i][j];

)

)

cout<<z，stepz,?++step<<，z:\n”;

output();

if(ans>=N)

break;

for(i=0;i<N;i++)

(

if(!R[i])

U[i]-=sigma;

if(T[i])

V[i]+=sigma;

for(j=0;j<N;j++)

(

if(T[j])

gt[i][j]+=sigma;

if(!R[i])

gt[i][j]-=sigma;

}

)

)

//////////////////////////////////////////////////////////

ans=0;

cout<<，，Result:，，?endl;

for(i=0;i<N;i++)

ans+=U[i]+V[i];

for(j=0;j<N;j++)

(

if(x[i]=j&&y[j]==i)cout?setw(2)<<U[i]+V[j]<<,

elsecout?setw(2)?0<<J';

)

cout?endl;

}

cout?，zMaximum:，，<<ans?endl;

)

return0;

)

input,txt:

5

41623

50376

23458

34634

46586

5

44436

11434

14535

56479

53683

5

78987

87676

96546

85764

76555

5

12345

67872

13445

36287

41354

/*

Problem:WeightedBipartiteMatching

Algorithm:HungarianAlgorithm

Reference:DouglasB.West,IntroductiontoGraphTheory,125-129

Author:PC

Date:2005.2.23

*/

#include<iostream.h>

#include<iomanip.h>

#include<fstream.h>

#include<memory.h>

ifstreamfin(〃input.txt〃);

#definecinfin

constintmax=50;

boolT[max],R[max],visited[max];

intU[max],V[max],gt[max][max],x[max],y[max];

intN;

voidoutput()

(

inti,j;

for(i=0;i<N;i++)

(

for(j=0;j<N;j++)

(

cout?setw(2)?gt[i][j]?,';

)

if(R[i])cout?setw(2)?,R'?'';

cout<<endl;

}

for(i=0;i<N;i++)

if(T[i])cout?setw(2)?,T*??';

elsecout?setw(2)'<<';

cout<<endl;

)

intpath(intu)

{

intv;

for(v=0;v<N;v++)

if(U[u]+V[v]-gt[u][v]==0&&!visited[v])

(

visited[v]=l;

if(y[v]<0||path(y[v]))

(

x[u]=v;y[v]=u;

R[u]=l;T[v]=O;

return1;

}else{

T[v]=l;

R[y[v]]=O；

)

)

)

return0;

}

intmain()

(

inti,j,ans,sigma,step=0;

for(;cin?N;){

for(i=0;i<N;i++)

(

U[i]=V[i]=0;

for(j=0;j<N;j++)

(

cin?gt[i][j];

if(U[i]<gt[i][j])U[i]=gt[i][j]：

)

)

//////////////////////////////////////////////////////////

for(;;)

(

ans=0;

sigma=0;

memset(x,-1,sizeof(x));

memset(y,-1,sizeof(y));

memset(R,0,sizeof(R));

memset(T,0,sizeof(T));

for(i=0;i<N;i++)

if(x[i]<0)

memset(visited,0,sizeof(visited));

ans+=path(i);

)

)

for(i=0;i<N;i++)

(

if(!R[i])

for(j=0;j<N;j++)

(

if(!T[jJ&&(sigma<l

sigma>U[i]+V[j]-gt[i][j]&&U[i]+V[j]-gt[i][j]>0))

sigma=U[i]+V[j]-gt[i][j];

)

)

cout?*step”<<++step<<":\n”;

output();

if(ans〉=N)

break;

for(i=0;i<N;i++)

(

if(!R[i])

U[i]-=sigma;

if(T[i])

V[i]+=sigma;

)

}