上一篇《數(shù)據(jù)庫(kù)入門級(jí)之算法【一】》中我們介紹了一些數(shù)據(jù)算法，現(xiàn)在我們繼續(xù)介紹一些基本排序算法。

冒泡排序

使用條件：集合的元素可對(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
        {  
            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<" ";  
    }  
    cout<
}  

性能分析：時(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ù)的話，那么這里增量就是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;  
   //通過這個(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
      {  
         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<" ";  
   }  
   cout<
}  

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

快速排序

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

算法思想：通過一趟排序?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
    {  
        while(*(b+high)>*(b+low)&&low--;  
        Sawp(b+low,b+high);  
        while(*(b+low)<*(b+high)&&low
        Sawp(b+low,b+high);  
    }  
    if(Old_low
    {  
        QuickSort(b,Old_low,low-1);  
    }  
    if(high+1
    {  
        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)

到這個(gè)，我們介紹了我們常見的基本數(shù)據(jù)查找和排序的算法，而這些是最基礎(chǔ)的算法，很多算法可以由他們延伸。

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

【編輯推薦】

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