上一篇《數據庫入門級之算法【一】》中我們介紹了一些數據算法，現在我們繼續介紹一些基本排序算法。

冒泡排序

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

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

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

性能分析：時間復雜度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
      {  
         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<
}  

性能分析：時間復雜度對于希爾排序就有點復雜，它根據具體的“增量”不同而不同，這里筆者采用嚴蔚敏《數據結構》的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
    {  
        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);  
    }  
}  
//交換函數  
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

【編輯推薦】

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