[[121968]]

筆者好長(zhǎng)時(shí)間沒(méi)有更新博客了，一個(gè)原因是開(kāi)發(fā)的項(xiàng)目所用到的技術(shù)都是老技術(shù)點(diǎn)，所接觸到的知識(shí)都是行業(yè)邏輯流程，所以只是自己做了總結(jié)并沒(méi)有拿上來(lái)分享。另外一個(gè)原因是目前筆者在重新學(xué)習(xí)C++語(yǔ)言以及計(jì)算機(jī)的一些基本知識(shí)（算法等）。

下面的代碼為C++代碼，好了直接進(jìn)入正題

編程基本算法（一）

編程基本算法（二）

編程基本算法（三） 

折半查找

又稱二分查找。

使用條件：有序集合。

算法思想：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或者不找到為止。

關(guān)鍵點(diǎn)在于比較中間位置所記錄的關(guān)鍵字和給定值的比較，如果比給定值大（這里假設(shè)集合從小到大排列）那么可以縮小區(qū)間范圍（集合開(kāi)始-->中間位置的上一位），在比較該區(qū)間的中間位置所記錄的關(guān)鍵字與給定值，依次循環(huán)到找到或者找不到位置。

舉例編程：這里有一個(gè)整數(shù)數(shù)據(jù) int a[10]={1,5,10,13,17,23,65,77,81,93};

（1）這是遞歸(感謝園友zdd指出這里判斷條件的錯(cuò)誤，應(yīng)該改為if(min>max)

//折半查找 
//數(shù)組必須按照一定的順序 
//參數(shù)：***，最小，目標(biāo)（參數(shù)類(lèi)型為整數(shù)） 
int BinarySearch(int min,int max,int num) 
{ 
if(min==max)return-1; 
int mid=(min+max)/2; 
if(a[mid]==num)return mid; 
elseif(a[mid]<num) 
{ 
return BinarySearch(mid+1,max,num); 
} 
else 
{ 
return BinarySearch(min,mid-1,num); 
} 
} 

（2）非遞歸

//非遞歸算法 
int BinarySearch_F(int num) 
{ 
int min=0; 
int max=9; 
int mid; 
while(min<=max) 
{ 
mid=(min+max)/2; 
if(a[mid]==num)return mid; 
elseif(a[mid]>num)max=mid-1; 
else min=mid+1; 
} 
return-1; 
} 

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

插入排序

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

算法思想：將一個(gè)記錄插入到已排好序的有序列中，從而得到一個(gè)新的，記錄數(shù)增1的有序序列。待插記錄依次比較已經(jīng)排好序列，如果序列數(shù)大于該待插記錄，那么該序列往后挪一位，直到找到序列小于待插記錄，那么此時(shí)插入到該序列的后一個(gè)位置，依次上面操作，直至插完位置。

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

//插入排序 
//這里temp是哨兵位 
//從小到大 
void InsertSort() { 
 int temp; 
 int j; 
 for(int i=1;i<10;i++) { 
 temp=b[i]; 
 for(j=i-1;j>=0;j--) { 
 if(b[j]>temp) { 
 b[j+1]=b[j]; 
 } 
 else { 
 break; 
 } 
 } 
 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ì)比大小的集合。

算法思想：基本思想與簡(jiǎn)單插入排序思想相似，唯一的不同點(diǎn)在于找出插入的位置，簡(jiǎn)單插入排序用的是依次比較，這里折半插入排序改進(jìn)了，將依次查找改進(jìn)成折半查找

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

void BinaryInsertSort() { 
 int temp,min,max,mid; int j; 
 for(int i=1;i<10;i++) {  
min=0;max=i-1; 
 temp=b[i]; 
 while(min<=max) { 
 mid=(min+max)/2; 
 if(b[mid]>temp) { 
 max=mid-1; } 
 else { min=mid+1; 
 } 
 } 
 for(j=i-1;j>=max+1;j--) { 
 b[j+1]=b[j]; 
 } 
 b[max+1]=temp; 
 } 
 cout<<"the sort is:"; 
 for(int i=0;i<10;i++) { 
 cout<<b[i]<<""; 
 } 
 cout<<endl; 
 } 

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

雖然這里時(shí)間復(fù)雜度與簡(jiǎn)單插入排序一樣，但是通過(guò)查找找到插入的位置用的比較次數(shù)是明顯減少的。

原文：http://www.cnblogs.com/couhujia/archive/2011/03/23/1991110.html