[[121970]]

在寫(xiě)此文章之前，筆者想說(shuō)說(shuō)關(guān)于程序員的基本知識(shí)，好多人在談?wù)撟约旱墓ぷ鹘?jīng)歷，或者給畢業(yè)生的建議，筆者贊同他們建議同學(xué)在學(xué)校里將計(jì)算機(jī)基礎(chǔ)打好，沒(méi)有良好基礎(chǔ)怎么能建大廈呢？有了一些基礎(chǔ)基本知識(shí)，在去學(xué)習(xí)深的理論 就是事半功倍了，如果是先遇到深理論在去學(xué)習(xí)相關(guān)的基礎(chǔ)，那就是事倍功半了。也許許多同學(xué)會(huì)說(shuō)，現(xiàn)在的很多企業(yè)都招能直接上手的，筆者首先想說(shuō)那種企業(yè)肯定是小企業(yè)，鼠目寸光，招也找不到很優(yōu)秀的人才，就算去了，這種人才也不會(huì)呆很長(zhǎng)時(shí)間，因?yàn)檫@種企業(yè)沒(méi)有發(fā)展的遠(yuǎn)見(jiàn)，有技術(shù)的人才可能因沒(méi)發(fā)展前途而跳槽。其次筆者想說(shuō)如果你有良好的計(jì)算機(jī)基礎(chǔ)，筆者相信你能成功在三個(gè)月之內(nèi)學(xué)習(xí)適應(yīng)達(dá)到企業(yè)技術(shù)要求。

其實(shí)，筆者想表達(dá)任何時(shí)候不要忽略基礎(chǔ)。閑話(huà)不多說(shuō)了，直接轉(zhuǎn)基本排序算法。

編程基本算法（一）

編程基本算法（二）

編程基本算法（三） 

冒泡排序

使用條件：集合的元素可對(duì)比大小

算法思想：連續(xù)地掃描待排序的記錄，每掃描一次，都會(huì)找出最小記錄，使之更接近頂部。由于每次掃描都會(huì)把一條記錄置于它的最終最正確的位置，因此下次掃描不需要重新檢查這條記錄

舉例編程：int b[10]={77,1,65,13,81,93,10,5,23,17}將其冒泡排序(這里筆者將概念弄混淆了，感謝zdd的指出）

//冒泡排序 
void Bubble(int b[10]) 
{ 
int temp; 
int i; 
for(i=9;i>0;i--) 
{ 
for(int j=0;j<i;j++) 
{ 
if(b[j]>b[j+1]) 
{ 
temp=b[j]; 
                b[j]=b[j+1]; 
                b[j+1]=temp; 
　　　　　　　} 
} 
} 
cout<<"the sort is:"; 
for(int i=0;i<10;i++) 
{ 
cout<<b[i]<<" "; 
} 
cout<<endl; 
} 

性能分析：時(shí)間復(fù)雜度O(n^2)

希爾排序

使用條件：集合的元素可對(duì)比大小

算法思想：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序“時(shí)，在對(duì)全體記錄進(jìn)行一次直接插入排序。 子序列構(gòu)成的不是簡(jiǎn)單“逐段分割”，而是相隔某個(gè)“增量”的記錄組成一個(gè)子序列。因此比較排序時(shí)候關(guān)鍵字較小的記錄就不是一步一步往前挪動(dòng)，而是相隔一定 增量移動(dòng)，該“增量”呈現(xiàn)一個(gè)遞減趨勢(shì)，最后這個(gè)“增量”總是為1，那么此時(shí)序列已基本有序，只要作少量的比較和移動(dòng)幾個(gè)完成排序。希爾排序不好把握增量 的設(shè)定。一般8個(gè)數(shù)我們認(rèn)為設(shè)定“增量”為：4,2,1。（這是一般希爾排序的設(shè)定）。那么筆者這里要擬定一個(gè)求“增量”的公式 h(n+1)=3*h(n)+1,（h>N/9停止）這個(gè)公式可能選擇增量不是最合適，但是卻適用一般“增量”的設(shè)定。如果是8個(gè)數(shù)的話(huà)，那么這里 增量就是1。

舉例編程：int b[10]={77,1,65,13,81,93,10,5,23,17}將其希爾排序

//希爾排序自增量需要自己合適選擇 
void ShellSort(int b[10]) 
{ 
int h,i; 
int n=10; 
//通過(guò)這個(gè)循環(huán)算出增量為1和4 
for(h=1;h<=n/9;h=3*h+1); 
 
//增量循環(huán) 
for(;h>0;h/=3) 
{ 
for(i=h;i<n;i++) 
{ 
int j,temp; 
temp=b[i]; 
//插入排序 
for(j=i-h;j>=0;j=j-h) 
{ 
if(b[j]>temp) 
{ 
b[j+h]=b[j]; 
} 
else 
{ 
break; 
} 
} 
b[j+h]=temp; 
} 
} 
cout<<"the sort is:"; 
for(int i=0;i<10;i++) 
{ 
cout<<b[i]<<" "; 
} 
cout<<endl; 
} 

性能分析：時(shí)間復(fù)雜度對(duì)于希爾排序就有點(diǎn)復(fù)雜，它根據(jù)具體的“增量”不同而不同，這里筆者采用嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》的O(n^3/2)

快速排序

使用條件：可對(duì)比大小的集合。

算法思想：通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)這種排序，最后 達(dá)到有序序列。這里有一個(gè)關(guān)鍵點(diǎn)，就是選取分割的“基準(zhǔn)”。肯定是大于這個(gè)“基準(zhǔn)”分成一個(gè)部分，小于這個(gè)“基準(zhǔn)”分成一個(gè)部分。這里筆者默認(rèn)取該部分第 一個(gè)記錄為“基準(zhǔn)”。

舉例編程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//快速排序 
void QuickSort(int *b,int low,int high) 
{ 
//交換函數(shù) 
void Sawp(int *a,int *b); 
int Old_low=low; 
int Old_high=high; 
while(low<high) 
{ 
while(*(b+high)>=*(b+low)&&low<high)high--; 
Sawp(b+low,b+high); 
while(*(b+low)=<*(b+high)&&low<high)low++; 
Sawp(b+low,b+high); 
} 
if(Old_low<low-1) 
{ 
QuickSort(b,Old_low,low-1); 
} 
if(high+1<Old_high) 
{ 
QuickSort(b,high+1,Old_high); 
} 
} 
 
//交換函數(shù) 
void Sawp(int *a,int *b) 
{ 
int temp; 
temp=*a; 
*a=*b; 
*b=temp; 
} 

性能分析：時(shí)間復(fù)雜度O(nlogn)

原文：http://www.cnblogs.com/couhujia/archive/2011/03/24/1993373.html