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

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

折半查找又稱二分查找。

使用條件：有序集合。

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

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

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

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

//折半查找  
//數(shù)組必須按照一定的順序  
//參數(shù)：***，最小，目標(biāo)（參數(shù)類型為整數(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;  
    else if(a[mid]
    {  
       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;  
        else if(a[mid]>num)max=mid-1;  
        else min=mid+1;  
    }  
    return -1;  
}　　  

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

插入排序

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

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

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

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

折半插入排序

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

算法思想：基本思想與簡單插入排序思想相似，唯一的不同點(diǎ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<" ";  
    }  
    cout<
}　　  

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

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

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

【編輯推薦】

1. 初探數(shù)據(jù)挖掘中的十大經(jīng)典算法
2. 當(dāng)今世界最受人們重視的十大經(jīng)典算法
3. 程序員須知之面試時算法題的解答思路