之前我們跟隨筆者重溫了數(shù)據(jù)結(jié)構(gòu)中的查詢算法和部分排序算法，現(xiàn)在我們繼續(xù)跟隨筆者繼續(xù)學(xué)習(xí)一些基本的排序算法。

選擇排序

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

算法思想：每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

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

//簡單選擇排序  
void SimpleSelect(int b[10])  
{  
    int temp;  
    int i;  
    for(i=0;i<9;i++)  
    {  
        for(int j=i+1;j<9;j++)  
        {  
            if(b[i]>b[j])  
            {  
                temp=b[i];  
                b[i]=b[j];  
                b[j]=temp;  
            }  
        }  
    }  
    cout<<"the sort is:";  
    for(int i=0;i<10;i++)  
    {  
        cout<<b[i]<<" ";  
    }  
    cout<<endl;  
}  

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

堆排序

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

算法思想：其實(shí)堆排序是簡單選擇排序的一種進(jìn)化，它最主要是減少比較的次數(shù)。什么是堆？若將序列對應(yīng)看成一個(gè)完全二叉樹，完全二叉樹中所有非終端節(jié)點(diǎn)的值均不大于（或者不小于）其左右孩子節(jié)點(diǎn)的值，可以稱作為堆。由堆的性質(zhì)可以知道堆頂是一個(gè)最大關(guān)鍵字(或者最小關(guān)鍵字)。在輸出堆頂后，使剩下的元素又建成一個(gè)堆，然后在輸出對頂。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程成便是堆排序。

堆排序主要分為兩個(gè)步驟：

1. 從無序序列建堆。
2. 輸出對頂元素，在調(diào)成一個(gè)新堆。

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

//堆排序  
void HeapSort(int b[10])  
{  
    void HeapAdjuest(int b[10],int min,int max);  
    void Sawp(int *a,int *b);  
    int i;  
    //因?yàn)槭峭瓿啥鏄?，所以從最后一個(gè)非葉子節(jié)點(diǎn)開始堆轉(zhuǎn)換  
    for(i=9/2;i>=0;i--)  
    {  
        HeapAdjuest(b,i,9);  
    }  
    //拿出堆頂數(shù)據(jù)在從新堆排序  
    for(i=9;i>0;i--)  
    {  
        Sawp(&b[i],&b[0]);  
        HeapAdjuest(b,0,i-1);  
    }  
}  
//堆調(diào)整(大頂堆)  
//min 數(shù)據(jù)需要調(diào)整在數(shù)組中的開始位置  
//max 數(shù)據(jù)需要調(diào)整在數(shù)據(jù)中的結(jié)束位置  
void HeapAdjuest(int b[10],int min,int max)  
{  
    if(max<=min)return ;  
    int temp;  
    temp=b[min];  
    int j;  
    //延它的孩子節(jié)點(diǎn)循環(huán)  
    for(j=2*min;j<=max;j*=2)  
    {  
        //選擇它的大孩子  
        if(j<max&&b[j]<b[j+1])  
        {  
            j++;  
        }  
        //堆頂小于它的孩子不做處理  
        if(temp>b[j])  
        {  
            break;  
        }  
        //將大的數(shù)替換成小的數(shù)  
        b[min]=b[j];  
        min=j;  
        }  
    b[min]=temp;  
}  
//交換函數(shù)  
void Sawp(int *a,int *b)  
{  
    int temp;  
    temp=*a;  
    *a=*b;  
    *b=temp;  
}  

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

歸并算法又稱2路歸并算法

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

算法思想：假設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長度為1，然后兩兩歸并，得到[n/2]個(gè)長度為2或者為1（這里長度為1可能這里序列長度是奇數(shù)，那么最后一個(gè)序列就落單了，所以長度為1）；在兩兩歸并，如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止。

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

//歸并排序  
void MergeSort(int b[10],int d[10],int min,int max)  
{  
    //用與存放中間分區(qū)域得到的序列  
    int c[10];  
    void Merge(int c[10],int d[10],int min,int mid,int max);  
    if(min==max)d[min]=b[min];  
    else 
    {  
        //平分成兩個(gè)區(qū)域  
        int mid=(min+max)/2;  
        //將這個(gè)區(qū)域進(jìn)行歸并排序  
        MergeSort(b,c,min,mid);  
        //將這個(gè)區(qū)域進(jìn)行歸并排序  
        MergeSort(b,c,mid+1,max);  
        //兩個(gè)區(qū)域歸并  
        Merge(c,d,min,mid,max);  
    }  
}  
//將有序序列d[min-mid]與d[mid+1-max]歸并成有序序列c[min-max]  
void Merge(int c[10],int d[10],int min,int mid,int max)  
{  
    int i,j,k;  
    for(i=j=min,k=mid+1;j<=mid&&k<=max;i++)  
    {  
        if(c[j]>c[k])  
        {  
            d[i]=c[k];  
            k++;  
        }  
        else 
        {  
            d[i]=c[j];  
            j++;  
        }  
    }  
    if(j<=mid)  
    {  
        for(;j<=mid;j++,i++)  
        {  
            d[i]=c[j];  
        }  
    }  
    if(k<=max)  
    {  
         for(;k<=max;k++,i++)  
        {  
            d[i]=c[k];  
        }  
    }  
}  

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

總結(jié)

因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用換進(jìn)和要求，選擇合適的排序方法考慮以下因素:

1. 待排序的記錄數(shù)n
2. 對其穩(wěn)定性要求
3. 存儲結(jié)構(gòu)
4. 時(shí)間和輔助空間復(fù)雜度

那么這么多排序算法，到底什么時(shí)候用什么樣的算法呢？

如果n比較?。ɡ鏽<=50),可采用直接插入排序或者簡單選擇排序。

如果序列初始狀態(tài)基本有序，則可選用直接插入排序，冒泡排序。

如果n比價(jià)大，則可采用時(shí)間復(fù)雜度為O(nlogn)的算法：快速排序，堆排序，歸并排序。

1. 快速排序被認(rèn)為目前基于比較的內(nèi)部排序中最好的方法。當(dāng)帶排序的關(guān)鍵字隨機(jī)分布時(shí)，快速排序平均時(shí)間最短。 不穩(wěn)定
2. 堆排序所需要的輔助空間小于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。 但還是比較不穩(wěn)定
3. 歸并排序，比較穩(wěn)定，但是歸并排序一般不提倡使用，實(shí)用性很差，占用的輔助空間肯能個(gè)比較大。

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

【編輯推薦】

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