[[121970]]

在寫此文章之前，筆者想說說關于程序員的基本知識，好多人在談論自己的工作經歷，或者給畢業生的建議，筆者贊同他們建議同學在學校里將計算機基礎打好，沒有良好基礎怎么能建大廈呢？有了一些基礎基本知識，在去學習深的理論 就是事半功倍了，如果是先遇到深理論在去學習相關的基礎，那就是事倍功半了。也許許多同學會說，現在的很多企業都招能直接上手的，筆者首先想說那種企業肯定是小企業，鼠目寸光，招也找不到很優秀的人才，就算去了，這種人才也不會呆很長時間，因為這種企業沒有發展的遠見，有技術的人才可能因沒發展前途而跳槽。其次筆者想說如果你有良好的計算機基礎，筆者相信你能成功在三個月之內學習適應達到企業技術要求。

其實，筆者想表達任何時候不要忽略基礎。閑話不多說了，直接轉基本排序算法。

編程基本算法（一）

編程基本算法（二）

編程基本算法（三） 

冒泡排序

使用條件：集合的元素可對比大小

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

舉例編程：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; 
} 

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

希爾排序

使用條件：集合的元素可對比大小

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

性能分析：時間復雜度對于希爾排序就有點復雜，它根據具體的“增量”不同而不同，這里筆者采用嚴蔚敏《數據結構》的O(n^3/2)

快速排序

使用條件：可對比大小的集合。

算法思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分關鍵字小，則可分別對這兩部分記錄繼續這種排序，最后 達到有序序列。這里有一個關鍵點，就是選取分割的“基準”。肯定是大于這個“基準”分成一個部分，小于這個“基準”分成一個部分。這里筆者默認取該部分第 一個記錄為“基準”。

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

//快速排序 
void QuickSort(int *b,int low,int high) 
{ 
//交換函數 
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); 
} 
} 
 
//交換函數 
void Sawp(int *a,int *b) 
{ 
int temp; 
temp=*a; 
*a=*b; 
*b=temp; 
} 

性能分析：時間復雜度O(nlogn)

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