數(shù)據(jù)庫入門級之算法【三】
之前我們跟隨筆者重溫了數(shù)據(jù)結(jié)構(gòu)中的查詢算法和部分排序算法，現(xiàn)在我們繼續(xù)跟隨筆者繼續(xù)學(xué)習(xí)一些基本的排序算法。
選擇排序
使用條件：可對比大小的集合。
算法思想：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(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;
- }
性能分析：時間復(fù)雜度為O（n^2）
堆排序
使用條件：可對比大小的集合。
算法思想：其實(shí)堆排序是簡單選擇排序的一種進(jìn)化，它最主要是減少比較的次數(shù)。什么是堆？若將序列對應(yīng)看成一個完全二叉樹，完全二叉樹中所有非終端節(jié)點(diǎn)的值均不大于（或者不小于）其左右孩子節(jié)點(diǎn)的值，可以稱作為堆。由堆的性質(zhì)可以知道堆頂是一個最大關(guān)鍵字(或者最小關(guān)鍵字)。在輸出堆頂后，使剩下的元素又建成一個堆，然后在輸出對頂。如此反復(fù)執(zhí)行，便能得到一個有序序列，這個過程成便是堆排序。
堆排序主要分為兩個步驟：
- 從無序序列建堆。
- 輸出對頂元素，在調(diào)成一個新堆。
舉例編程：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)槭峭瓿啥鏄洌詮淖詈笠粋€非葉子節(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;
- }
性能分析：時間復(fù)雜度時間復(fù)雜度O(nlogn)
歸并算法又稱2路歸并算法
使用條件：可對比大小的集合。
算法思想：假設(shè)初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1，然后兩兩歸并，得到[n/2]個長度為2或者為1（這里長度為1可能這里序列長度是奇數(shù)，那么最后一個序列就落單了，所以長度為1）；在兩兩歸并，如此重復(fù)，直至得到一個長度為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
- {
- //平分成兩個區(qū)域
- int mid=(min+max)/2;
- //將這個區(qū)域進(jìn)行歸并排序
- MergeSort(b,c,min,mid);
- //將這個區(qū)域進(jìn)行歸并排序
- MergeSort(b,c,mid+1,max);
- //兩個區(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];
- }
- }
- }
性能分析：時間復(fù)雜度O(nlogn)
總結(jié)
因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用換進(jìn)和要求，選擇合適的排序方法考慮以下因素:
- 待排序的記錄數(shù)n
- 對其穩(wěn)定性要求
- 存儲結(jié)構(gòu)
- 時間和輔助空間復(fù)雜度
那么這么多排序算法，到底什么時候用什么樣的算法呢？
如果n比較小（例如n<=50),可采用直接插入排序或者簡單選擇排序。
如果序列初始狀態(tài)基本有序，則可選用直接插入排序，冒泡排序。
如果n比價(jià)大，則可采用時間復(fù)雜度為O(nlogn)的算法：快速排序，堆排序，歸并排序。
- 快速排序被認(rèn)為目前基于比較的內(nèi)部排序中最好的方法。當(dāng)帶排序的關(guān)鍵字隨機(jī)分布時，快速排序平均時間最短。 不穩(wěn)定
- 堆排序所需要的輔助空間小于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。 但還是比較不穩(wěn)定
- 歸并排序，比較穩(wěn)定，但是歸并排序一般不提倡使用，實(shí)用性很差，占用的輔助空間肯能個比較大。
原文鏈接：http://www.cnblogs.com/couhujia/archive/2011/03/25/1994996.html
【編輯推薦】
