排序演算法小結

kuaisuppaixu

fjoiesdnklt最近經常碰到排序演算法，以前也碰到應用過並完整的理解了一遍，但是好記性不如爛筆頭，何況是我這三秒記憶，所以除了大概有一些印象外什麼東東都不記得了，還是需要記錄一下加深印象並且用演算法實現一遍。聽起來工程量很是浩大呀！好吧，開始吧，皮卡丘！

排序分為內排序和外排序；

內排序：在排序期間排序對象全部放置在內存中。

外排序：由於排序對象過多，內存中放不下，在排序過程中排序對象一直在內外內存之間移動的排序。

內排序的方法有很多種，根據所用策略不多可以分為一下幾種

穩定排序：若排序中有一些相同的元素，在排序過程中，這些相同元素的相對位置沒有變化。

穩定排序包括：冒泡，插入，基數，歸併

不穩定排序包括：選擇，快排，希爾，堆

先說一些最基本的排序演算法，他們的時間複雜度都是n^2：

1，冒泡排序：冒泡排序很容易想到魚吐泡泡，就是最大的那個元素浮上去，每次都把未排序的元素的最大值找出來。採用的是兩兩對比的方法，一直對比a[i]與a[i+1]。

待排序數據為N，則需要大循環N-1次，每次循環都要進行N-i次小循環（i表示第i次大循環），其實現演算法為：

//冒泡排序private E[] BubbleSort(E[] array,N){E e;for(int i=0;i<N-2;i++){//大循環N-1次for(int j=0;j<N-2-i;j++){//小循環N-1-i次if(array[j]>array[j+1]){//若是前者大於後者則兩者交換位置e=array[j+1];array[j+1]=array[j];array[j]=e;}}}return array;}

冒泡演算法是幾種演算法中效果較差的，尤其是在大數據時，由演算法可知每一次排序需要（N-1）+（N-2）+...+1次，每一次操作需要進行一次比較和三次賦值。

2，直接選擇排序

直接選擇排序，顧名思義，就是選擇出最大的值，然後和array[n-1]元素交換位置。這個演算法主要是進行比較較多，交換步驟少。實現步驟如下：

待排序數據為N，則需要大循環N-1次，每次循環都要進行N-i次小循環（i表示第i次大循環），其實現演算法為：

//直接選擇排序private E[] SelectionSort(E[] array,N){E e=array[0];int location=0;for(int i=0;i<N-2;i++){//大循環N-1次for(int j=0;j<N-1-i;j++){//小循環N-i次if(array[j]>e){//若是前者大於後者則將array[j]賦給e，e記錄最大值e=array[j];location=j;}}array[location]=array[N-i-1];array[N-i-1]=e;}return array;}

直接選擇排序演算法的對比較多，交換少，若是對比較難的數據類型不適合使用（如字元串）

3，直接插入排序：插入排序由N-1趟排序組成，它需要保證在第p趟排序時從0-p位置上的元素必須已經為排序狀態。如圖所示

待排序數據為N，則需要大循環N-1次，每次大循環進行的小循環次數不定，當待排序元素找到他的位置後就跳出小循環，其實現演算法為：

//直接插入排序private E[] SelectionSort(E[] array,N){E e;for(int i=0;i<N-2;i++){//大循環N-1次for(int j=0;j<i+1;j++){//小循環i+1次if(array[i+1]<array[j]){//若是待排序元素小於array[j]就尋找完成e=array[i+1];//並將array[i+1和array[j]交換位置array[i+1]=array[j];array[j]=e;break;//完成尋找後跳出小循環}}}return array;}

這種演算法是穩定排序演算法，同時也是這三種最簡單排序中最快的一種。

接下來要看幾種高級演算法。這幾種演算法都比前面幾種難，但是對於數據較多的時候，其效率會高很多。

1，希爾排序演算法

希爾演算法屬於插入法的一種，是由直接插入演算法改進而來的。先將一大段無序元素分成若干個子序列分別進行插入排序。

比如一段長度為N的元素，先令d1=N/2；每隔d1個間隔的元素為一組。每一小組進行直接插入排序，再整合成一段，再令d2=d1/2，重複上述步驟直至di=1。具體實施如下：

實現程序為：

//希爾排序private void ShellSort(E array[]){for(int gap=array.length/2;gap>0;gap=gap/2){這個大循環表示分組次數for(int i=gap;i<a.length;i++){E e=a[i];for(j=i;j>=gap&&e.compareTo(a[j-gap])<0;j=j-gap){a[j]=a[j-gap];a[j-gap]=e;//感覺有問題不應該是a[j-gap]?}}}}

希爾排序的增量dl有很多種選擇方法，這種二分法不一定就是最快的排序方法。希爾排序演算法是高級排序演算法中最容易實現的。在大批量的排序中適合使用。

2，堆排序

堆排序首先應該對堆有一定的認識。堆是一種數據結構，由二叉樹演變來的。它應用到了二叉樹中的最小（大）完全二叉樹。最小（最大）完全二叉樹的特性為父節點永遠小於（大於）左右子節點。他的操作步驟如下。假設以最大完全二叉樹來實現：

按步驟來一步一步將根值移至未排序堆的末尾。這裡重複步驟只有兩個，一個是將根節點與未排序末節點值對換。另一步就是堆的重排。實現程序如下：

//堆排序private void DeleteMax(Node[] t,int size){E x;x=t[0];//取出最大元素E last=t[--size];//last為未排序堆最後的元素//重建堆int i=0；}

3.快速排序：快排是冒泡演算法的改進演算法。

首先任選一個元素為支點，一般是第一個元素。然後根據大於小於該支點的不同將元素放置在支點前後兩個區域。這就是一次快排。此時這些元素分成了兩個子序列。接下來，對兩個子序列分別採用快排。此時分成了四個子序列。一直分到各子序列長度為1截止。具體操作步驟如下：

先將a[0]中的數保存到X中，可以理解成在數組a[0]上挖了個坑，可以將其它數據填充到這來。從j開始向前找一個比X小或等於X的數（在例子中j從9開始）。當j=8時，符合條件，將a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++（i從0開始）; 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎麼辦了？簡單，再找數字來填a[8]這個坑。這次從i開始向後找一個大於X的數，當i=2，符合條件，將a[2]挖出再填到上一個坑中a[8]=a[2]; j--;一直如此循環直至每一個序列只有一個元素。實現程序如下：

//快速排序private void quickSort(E e[],int f,int b){E x=e[f];//取出第一個比較元素，在第一個位置挖上坑if(f>=b)return;//當小序列元素數為1時停止排序int i=f;j=b+1;while(true){while(e[--j].compareTo(x)>0&&i<j);//從後到前找小於支點的數e[i]=e[j];while(e[++i].compareTo(x)<0&&i<j);//從前到後找大於支點的數e[j]=e[i];if(i>j){break;}}e[j]=x;//將支點賦給e[j]quickSort(e[],0,j-1);//遞歸quichSort(e[],j+1,b);}

快排被認為是最快的內排序演算法，但是快排由於遞歸需要額外區間，因此可能發生溢出。同時它對於小額數據和已經較有序數據排序效果差，因而選擇時需慎重。

4，二路歸併排序

歸併，顧名思義，就是一個歸為二，二歸為四。。。當然也可以不是以二的倍數歸併，但是二路歸併比較常見。首先還是了解一下他是怎麼實現的。

//二路歸併排序private void MergeSort(E e[],int size){//size為E的大小int s=1;//從一歸二開始歸併while(s<size){MergePass(e,b,s,size);s+=s;MergePass(b,a,s,size);s+=s;}if(b) delete[] b;}private MergePass(E x[],E y[],int s,int n){//歸併大小為s的子序列int i=0;int t=s+s;while(i<n-t){Merge(x,y,i,i+s-1,i_t-1);i=i+t;}//剩下元素不足2sif(i+s<n){Merge(x,y,i,i+s-1,n-1);}else{for(int j=i;j<=n-1;j++){y[j]=x[j];}}}private void Merge(E c[],E d[],int l, int m, int r){//合併c[l:m]和c[m:r]到d[l:r]int i=l;int j=m+1;int k=l;while((i<=m)&&(j<=r)){if(c[i]<c[j]){d[k++]=c[j++];}}if(i>m){for(int q=j;q<=r;q++){d[k++]=c[q];}}else{for(int q=i;q<=m;q++){d[k++]=c[q];}}}

上述演算法都是通過元素比較來實現的。從理論上來說都需要進行至少log（N）次比較。因而最有時間複雜度為Nlog（N）。而不需要進行比較的排序方法時間將為線性級別（N）。

分配排序就是不需要比較的排序方法。包括箱子排序和基數排序。

箱排序又叫桶排序，將關鍵字等於k的元素放在第k個箱子，再將非空箱子按順序相連。

箱子排序適合於一些元素值在一定範圍的排序，比如年齡，學號等。

實現代碼為：

//箱子排序（桶排序）private void BinSort(E e[],int N,int range,){int b[]=new int[range+1];E sort[]=new E[N];int temp=0;sun=0;//將箱子置空for(i=0;i<=range;i++){b[i]=0;}//統計每個箱子該有多大for(int i=0;i<n;i++){b[value(e[i])]++;}//根據每個箱子大小計算放置位置for(int i=0;i<=range;i++){if(b[i]!=0){temp=b[i];b[i]=sum;sum=sum+temp;}}//根據a[i]值尋找所在箱子for(int i=0;i<n;i++){sort[b[value(a[i])]++]=a[i];}}

暫時就先總結到這吧，個人感覺，堆排序和二路歸併排序的程序最難搞定。桶排序和快排給了我很大的驚喜！看到這個演算法的時候我是眼睛冒星星的（嘻嘻）