各种排序算法及其实现总结
排序算法總結
?
1.插入排序
一般來說，插入排序 都采用in-place在數組上實現。具體算法描述如下：
從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置中
重復步驟2
如果比較操作 的代價比交換操作 大的話，可以采用二分查找法 來減少比較操作 的數目。該算法可以認為是插入排序 的一個變種，稱為二分查找排序 。
上代碼：
view plaincopy to clipboardprint?
void insertsort(int array[],int n)??
{??
??? int i,j,temp;??
??? for(i=1;i<n;i++)??
??? {??
??????? temp=array[i];??
??????? j=i-1;??
??????? while((j>=0) && (array[j]>temp))??
??????? {??
??????????? array[j+1]=array[j];??
??????????? j--;??
??????? }??
??????? array[j+1]=temp;??
??? }??
}?
算法復雜度：???
如果目標是把n個元素的序列升序排列，那么采用插入排序 存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1) 次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2 次。插入排序 的賦值操作是比較操作的次數加上(n-1) 次。平均來說插入排序 算法復雜度為O(n 2 )。因而，插入排序 不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序 還是一個不錯的選擇。
2.希爾排序
希爾排序（Shell Sort）又叫做縮小增量排序（diminishing increment sort），是一種很優秀的排序法，算法本身不難理解，也很容易實現，而且它的速度很快。
插入排序（Insertion Sort） 的一個重要的特點是，如果原始數據的大部分元素已經排序，那么插入排序的速度很快（因為需要移動的元素很少）。從這個事實我們可以想到，如果原始數據只有很少元素，那么排序的速度也很快。－－希爾排序就是基于這兩點對插入排序作出了改進。
例如，有100個整數需要排序。
第一趟排序先把它分成50組，每組2個整數，分別排序。
第二趟排序再把經過第一趟排序后的100個整數分成25組，每組4個整數，分別排序。
第三趟排序再把前一次排序后的數分成12組，第組8個整數，分別排序。
照這樣子分下去，最后一趟分成100組，每組一個整數，這就相當于一次插入排序。
由于開始時每組只有很少整數，所以排序很快。之后每組含有的整數越來越多，但是由于這些數也越來越有序，所以排序速度也很快。
下面用C語言實現希爾排序，用的是K&R里的算法，該算法結構很清晰。
view plaincopy to clipboardprint?
void shellsort(int array[],int n)??
{??
??? int gap,i,j,temp;??
??? for(gap=n/2;gap>0;gap/=2)??
??? {??
??????? for(i=gap;i<n;i++)??
??????? {??
??????????? for(j=i-gap;j>=0 && array[j]>array[j+gap];j-=gap)??
??????????? {??
??????????????? temp=array[j];??
??????????????? array[j]=array[j+gap];??
??????????????? array[j+gap]=temp;??
??????????? }??
??????? }??
??? }??
}?
3.快速排序
快速排序使用分治法 （Divide and conquer）策略來把一個序列 （list）分為兩個子序列（sub-lists）。
步驟為：
從數列中挑出一個元素，稱為 "基準"（pivot），
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分割之后，該基準是它的最后位置。這個稱為分割（partition） 操作。
遞歸 地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
view plaincopy to clipboardprint?
void quickSort(int a[],int low,int high)??
{?????
??? int i,j,pivot;??
??? if(low<high)??
??? {??
?????? pivot=a[low];??
?????? i=low;??
?????? j=high;??
?????? while(i<j)??
?????? {??
????????? while(i<j && a[j]>=pivot)??
????????????? j--;??
????????? if(i<j)??
????????????? a[i++]=a[j];??
????????? while(i<j && a[i]<=pivot)??
????????????? i++;??
????????? if(i<j)??
????????????? a[j--]=a[i];??
?????? }??
?????? a[i]=pivot;??
?????? quickSort(a,low,i-1);??
?????? quickSort(a,i+1,high);??
??? }??
}??
4.堆排序
通常堆積樹(heap)是通過一維陣列 來實現的。在起始陣列為 0 的情形中：
堆積樹的根節點（即堆積樹的最大值）存放在陣列位置 1 的地方
注意：不使用位置 0，否則左子樹永遠為 0 參考
節點i的左子節點在位置（2*i）
節點i的右子節點在位置（2*i+1）
節點i的父節點在位置floor((i-1)/2)
在堆積樹的數據結構中，堆積樹中的最大值總是位于根節點。堆積樹中定義以下幾種操作：
最大堆積調整（Max_Heapify）：將堆積樹的末端子結點作調整,使得子結點永遠小于父結點
建立最大堆積（Build_Max_Heap）：將堆積樹所有數據重新排序
堆積排序（HeapSort）：移除位在第一個數據的根結點,并做最大堆積調整的遞歸 運算
view plaincopy to clipboardprint?
int parent(int i)??
{??
??? return (int)floor(i/2);??
}??
int left(int i)??
{??
??? return 2*i;??
}??
int right(int i)??
{??
??? return 2*i+1;??
}??
void max_heapify(int a[],int i,int heap_size)??
{??
??? int l=left(i);??
??? int r=right(i);??
??? int largest,temp;??
??? if(l<heap_size && a[l]>a[i])??
??? {??
??????? largest=l;??
??? }??
??? else??
??? {??
??????? largest=i;??
??? }??
??? if(r<heap_size && a[r]>a[largest])??
??? {??
??????? largest=r;??
??? }??
??? if(largest != i)??
??? {??
??????? temp=a[i];??
??????? a[i]=a[largest];??
??????? a[largest]=temp;??
??????? max_heapify(a,largest,heap_size);??
??? }??
}??
void build_max_heap(int a[])??
{??
??? int i;??
??? for(i=7;i>=0;i--)??
??? {??
??????? max_heapify(a,i,7);??
??? }??
}??
void print(int a[])??
{??
??? int i;??
??? for(i=0;i<7;i++)??
??? {??
??????? printf("%3d",a[i]);??
??? }??
??? printf("/n");??
}??
void heapsort(int a[],int heap_size)??
{??
??? build_max_heap(a);??
??? int temp,i;??
??? for(i=heap_size-1;i>=1;i--)??
??? {??
??????? temp=a[0];??
??????? a[0]=a[i];??
??????? a[i]=temp;??
??????? heap_size=heap_size-1;??
??????? max_heapify(a,0,heap_size);??
??? }??
??? print(a);??
}?
5.歸并排序
歸并操作(merge)，也叫歸并算法，指的是將兩個已經排序的序列合并成一個序列的操作。
歸并操作的工作原理如下：
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
view plaincopy to clipboardprint?
static void merge(int array[], int p, int q, int r)??
?{??
??? int i,k;??
??? int begin1,end1,begin2,end2;??
??? int* temp = new int [r-p+1]; //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列??
??? begin1= p;???? end1 = q; //設定兩個指針，最初位置分別為兩個已經排序序列的起始位置??
??? begin2 = q+1;? end2 = r;??
???
??? k = 0;??
??? while((begin1 <= end1)&&( begin2 <= end2)) //比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置??
??? {??
??????? if(array[begin1]<array[begin2])??
??????? {??
??????????? temp[k] = array[begin1];? begin1++;???
??????? }??
??????? else??
??????? {??
??????????? temp[k] = array[begin2];? begin2++;??
??????? }??
??????? k++;??????????
??? }??
???
??? while(begin1<=end1) //若第一個序列有剩余，直接拷貝出來粘到合并序列尾??
??? {??
??????? temp[k++] = array[begin1++];??
??? }??
??? while(begin2<=end2) //若第二個序列有剩余，直接拷貝出來粘到合并序列尾??
??? {??
??????? temp[k++] = array[begin2++];??
??? }??
??? for (i = 0; i < (r - p +1); i++) //將排序好的序列拷貝回數組中??
??????? array[p+i] = temp[i];??
??? delete[] (temp);???
?}??
歸并排序具體工作原理如下（假設序列共有n個元素）：
將序列每相鄰兩個數字進行歸并操作（merge），形成f l o o r (n / 2) 個序列，排序后每個序列包含兩個元素
將上述序列再次歸并，形成f l o o r (n / 4) 個序列，每個序列包含四個元素
重復步驟2，直到所有元素排序完畢
view plaincopy to clipboardprint?
void merge_sort(int array[], unsigned int first, unsigned int last)
?
{
?
??? int mid = 0;
?
??? if(first<last)
?
??? {
?
??????? mid = (first+last)/2;
?
??????? merge_sort(array, first, mid);
?
??????? merge_sort(array, mid+1,last);
?
??????? merge(array,first,mid,last);
?
??? }
?
}
轉載聲明： 本文轉自 http://blog.csdn.net/tqyou85/archive/2009/09/28/4600980.aspx
?
===============================================================================
?
排序算法總結
?
排序算法是一種基本并且常用的算法。由于實際工作中處理的數量巨大，所以排序算法對算法本身的速度要求很高。
??? 而一般我們所謂的算法的性能主要是指算法的復雜度，一般用O方法來表示。在后面我將給出詳細的說明。
??? 對于排序的算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。
??? 我將按照算法的復雜度，從簡單到難來分析算法。
??? 第一部分是簡單排序算法，后面你將看到他們的共同點是算法復雜度為O(N*N)（因為沒有使用word,所以無法打出上標和下標）。
??? 第二部分是高級排序算法，復雜度為O(Log2(N))。這里我們只介紹一種算法。另外還有幾種算法因為涉及樹與堆的概念，所以這里不于討論。
??? 第三部分類似動腦筋。這里的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較奇特，值得參考（編程的角度）。同時也可以讓我們從另外的角度來認識這個問題。
??? 第四部分是我送給大家的一個餐后的甜點——一個基于模板的通用快速排序。由于是模板函數可以對任何數據類型排序（抱歉，里面使用了一些論壇專家的呢稱）。
???
??? 現在，讓我們開始吧：
???
一、簡單排序算法
由于程序比較簡單，所以沒有加什么注釋。所有的程序都給出了完整的運行代碼，并在我的VC環境
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平臺上應該也不會有什么
問題的。在代碼的后面給出了運行過程示意，希望對理解有幫助。
1.冒泡法：
這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
??? int iTemp;
??? for(int i=1;i<Count;i++)
??? {
??????? for(int j=Count-1;j>=i;j--)
??????? {
??????????? if(pData[j]<pData[j-1])
??????????? {
??????????????? iTemp = pData[j-1];
??????????????? pData[j-1] = pData[j];
??????????????? pData[j] = iTemp;
??????????? }
??????? }
??? }
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4};
??? BubbleSort(data,7);
??? for (int i=0;i<7;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
倒序(最糟情況)
第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)
第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
上面我們給出了程序段，現在我們分析它：這里，影響我們算法性能的主要部分是循環和交換，
顯然，次數越多，性能就越差。從上面的程序我們可以看出循環的次數是固定的，為1+2+...+n-1。
寫成公式就是1/2*(n-1)*n。
現在注意，我們給出O方法的定義：
??? 若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n) = O(g(n))。（呵呵，不要說沒
學好數學呀，對于編程數學是非常重要的！！！）
現在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我們程序循環的復雜度為O(n*n)。
??? 再看交換。從程序后面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換本身同數據源的有序程度有極大的關系，當數據處于倒序的情況時，交換次數同循環一樣（每次循環判斷都會交換），復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。亂序時處于中間狀態。正是由于這樣的原因，我們通常都是通過循環次數來對比算法。
2.交換法：
交換法的程序最清晰簡單，每次用當前的元素一一的同其后的元素比較并交換。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
??? int iTemp;
??? for(int i=0;i<Count-1;i++)
??? {
??????? for(int j=i+1;j<Count;j++)
??????? {
??????????? if(pData[j]<pData[i])
??????????? {
??????????????? iTemp = pData[i];
??????????????? pData[i] = pData[j];
??????????????? pData[j] = iTemp;
??????????? }
??????? }
??? }
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4};
??? ExchangeSort(data,7);
??? for (int i=0;i<7;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,9,10,8->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交換1次)
第二輪：7,10,8,9->7,8,10,9->7,8,10,9(交換1次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣也是1/2*(n-1)*n，所以算法的復雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。
3.選擇法：
現在我們終于可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下）這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從省下的部分中選擇最小的與第二個交換，這樣往復下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
??? int iTemp;
??? int iPos;
??? for(int i=0;i<Count-1;i++)
??? {
??????? iTemp = pData[i];
??????? iPos = i;
??????? for(int j=i+1;j<Count;j++)
??????? {
??????????? if(pData[j]<iTemp)
??????????? {
??????????????? iTemp = pData[j];
??????????????? iPos = j;
??????????? }
??????? }
??????? pData[iPos] = pData[i];
??????? pData[i] = iTemp;
??? }
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4};
??? SelectSort(data,7);
??? for (int i=0;i<7;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
倒序(最糟情況)
第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次)
第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)
第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次)
循環次數：6次
交換次數：2次
其他：
第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1次)
第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次)
第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
遺憾的是算法需要的循環次數依然是1/2*(n-1)*n。所以算法復雜度為O(n*n)。
我們來看他的交換。由于每次外層循環只產生一次交換（只有一個最小值）。所以f(n)<=n
所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。
4.插入法：
插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然后繼續下一張
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
??? int iTemp;
??? int iPos;
??? for(int i=1;i<Count;i++)
??? {
??????? iTemp = pData[i];
??????? iPos = i-1;
??????? while((iPos>=0) && (iTemp<pData[iPos]))
??????? {
??????????? pData[iPos+1] = pData[iPos];
??????????? iPos--;
??????? }
??????? pData[iPos+1] = iTemp;
??? }
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4};
??? InsertSort(data,7);
??? for (int i=0;i<7;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7(交換1次)(循環1次)
第二輪：9,10,8,7->8,9,10,7(交換1次)(循環2次)
第一輪：8,9,10,7->7,8,9,10(交換1次)(循環3次)
循環次數：6次
交換次數：3次
其他：
第一輪：8,10,7,9->8,10,7,9(交換0次)(循環1次)
第二輪：8,10,7,9->7,8,10,9(交換1次)(循環2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)(循環1次)
循環次數：4次
交換次數：2次
上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中最好的，其實不是，
因為其循環次數雖然并不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單
排序的不同，交換次數仍然可以這樣推導）?，F在看交換，從外觀上看，交換次數是O(n)（推導類似
選擇法），但我們每次要進行與內層循環相同次數的‘=’操作。正常的一次交換我們需要三次‘=’
而這里顯然多了一些，所以我們浪費了時間。
最終，我個人認為，在簡單排序算法中，選擇法是最好的。
二、高級排序算法：
高級排序算法中我們將只介紹這一種，同時也是目前我所知道（我看過的資料中）的最快的。
它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數組中間值，然后
把比它小的放在左邊，大的放在右邊（具體的實現是從兩邊找，找到一對后交換）。然后對兩邊分別使
用這個過程（最容易的方法——遞歸）。
1.快速排序：
#include <iostream.h>
void run(int* pData,int left,int right)
{
??? int i,j;
??? int middle,iTemp;
??? i = left;
??? j = right;
??? middle = pData[(left+right)/2];? //求中間值
??? do{
??????? while((pData[i]<middle) && (i<right))//從左掃描大于中值的數
??????????? i++;??????????
??????? while((pData[j]>middle) && (j>left))//從右掃描大于中值的數
??????????? j--;
??????? if(i<=j)//找到了一對值
??????? {
??????????? //交換
??????????? iTemp = pData[i];
??????????? pData[i] = pData[j];
??????????? pData[j] = iTemp;
??????????? i++;
??????????? j--;
??????? }
??? }while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
??? //當左邊部分有值(left<j)，遞歸左半邊
??? if(left<j)
??????? run(pData,left,j);
??? //當右邊部分有值(right>i)，遞歸右半邊
??? if(right>i)
??????? run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
??? run(pData,0,Count-1);
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4};
??? QuickSort(data,7);
??? for (int i=0;i<7;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。
第一層遞歸，循環n次，第二層循環2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法復雜度為O(log2(n)*n)
其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變
成交換法（由于使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全
不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。
如果你擔心這個問題，你可以使用堆排序，這是一種穩定的O(log2(n)*n)算法，但是通常情況下速度要慢于快速排序（因為要重組堆）。
三、其他排序
1.雙向冒泡：
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。
代碼看起來復雜，仔細理一下就明白了，是一個來回震蕩的方式。
寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換（我不這么認為，也許我錯了）。
反正我認為這是一段有趣的代碼，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
??? int iTemp;
??? int left = 1;
??? int right =Count -1;
??? int t;
??? do
??? {
??????? //正向的部分
??????? for(int i=right;i>=left;i--)
??????? {
??????????? if(pData[i]<pData[i-1])
??????????? {
??????????????? iTemp = pData[i];
??????????????? pData[i] = pData[i-1];
??????????????? pData[i-1] = iTemp;
??????????????? t = i;
??????????? }
??????? }
??????? left = t+1;
??????? //反向的部分
??????? for(i=left;i<right+1;i++)
??????? {
??????????? if(pData[i]<pData[i-1])
??????????? {
??????????????? iTemp = pData[i];
??????????????? pData[i] = pData[i-1];
??????????????? pData[i-1] = iTemp;
??????????????? t = i;
??????????? }
??????? }
??????? right = t-1;
??? }while(left<=right);
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4};
??? Bubble2Sort(data,7);
??? for (int i=0;i<7;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
2.SHELL排序
這個排序非常復雜，看了程序就知道了。
首先需要一個遞減的步長，這里我們使用的是9、5、3、1（最后的步長必須是1）。
工作原理是首先對相隔9-1個元素的所有內容排序，然后再使用同樣的方法對相隔5-1個元素的排序
以次類推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
??? int step[4];
??? step[0] = 9;
??? step[1] = 5;
??? step[2] = 3;
??? step[3] = 1;
??? int iTemp;
??? int k,s,w;
??? for(int i=0;i<4;i++)
??? {
??????? k = step[i];
??????? s = -k;
??????? for(int j=k;j<Count;j++)
??????? {
??????????? iTemp = pData[j];
??????????? w = j-k;//求上step個元素的下標
??????????? if(s ==0)
??????????? {
??????????????? s = -k;
??????????????? s++;
??????????????? pData[s] = iTemp;
??????????? }
??????????? while((iTemp<pData[w]) && (w>=0) && (w<=Count))
??????????? {
??????????????? pData[w+k] = pData[w];
??????????????? w = w-k;
??????????? }
??????????? pData[w+k] = iTemp;
??????? }
??? }
}
void main()
{
??? int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
??? ShellSort(data,12);
??? for (int i=0;i<12;i++)
??????? cout<<data[i]<<" ";
??? cout<<"/n";
}
呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使用0
步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。
這個算法的得名是因為其發明者的名字D.L.SHELL。依照參考資料上的說法：“由于復雜的數學原因
避免使用2的冪次步長，它能降低算法效率?！绷硗馑惴ǖ膹碗s度為n的1.2次冪。同樣因為非常復雜并
“超出本書討論范圍”的原因（我也不知道過程），我們只有結果了。
四、基于模板的通用排序：
這個程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。
MyData.h文件
///
class CMyData?
{
public:
??? CMyData(int Index,char* strData);
??? CMyData();
??? virtual ~CMyData();
??? int m_iIndex;
??? int GetDataSize(){ return m_iDataSize; };
??? const char* GetData(){ return m_strDatamember; };
??? //這里重載了操作符：
??? CMyData& operator =(CMyData &SrcData);
??? bool operator <(CMyData& data );
??? bool operator >(CMyData& data );
private:
??? char* m_strDatamember;
??? int m_iDataSize;
};
MyData.cpp文件
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
??? if(m_strDatamember != NULL)
??????? delete[] m_strDatamember;
??? m_strDatamember = NULL;
}
CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
??? m_iDataSize = strlen(strData);
??? m_strDatamember = new char[m_iDataSize+1];
??? strcpy(m_strDatamember,strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
??? m_iIndex = SrcData.m_iIndex;
??? m_iDataSize = SrcData.GetDataSize();
??? m_strDatamember = new char[m_iDataSize+1];
??? strcpy(m_strDatamember,SrcData.GetData());
??? return *this;
}
bool CMyData::operator <(CMyData& data )
{
??? return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
??? return m_iIndex>data.m_iIndex;
}
///
//
//主程序部分
#include <iostream.h>
#include "MyData.h"
template <class T>
void run(T* pData,int left,int right)
{
??? int i,j;
??? T middle,iTemp;
??? i = left;
??? j = right;
??? //下面的比較都調用我們重載的操作符函數
??? middle = pData[(left+right)/2];? //求中間值
??? do{
??????? while((pData[i]<middle) && (i<right))//從左掃描大于中值的數
??????????? i++;??????????
??????? while((pData[j]>middle) && (j>left))//從右掃描大于中值的數
??????????? j--;
??????? if(i<=j)//找到了一對值
??????? {
??????????? //交換
??????????? iTemp = pData[i];
??????????? pData[i] = pData[j];
??????????? pData[j] = iTemp;
??????????? i++;
??????????? j--;
??????? }
??? }while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
??? //當左邊部分有值(left<j)，遞歸左半邊
??? if(left<j)
??????? run(pData,left,j);
??? //當右邊部分有值(right>i)，遞歸右半邊
??? if(right>i)
??????? run(pData,i,right);
}
template <class T>
void QuickSort(T* pData,int Count)
{
??? run(pData,0,Count-1);
}
void main()
{
??? CMyData data[] = {
??????? CMyData(8,"xulion"),
??????? CMyData(7,"sanzoo"),
??????? CMyData(6,"wangjun"),
??????? CMyData(5,"VCKBASE"),
??????? CMyData(4,"jacky2000"),
??????? CMyData(3,"cwally"),
??????? CMyData(2,"VCUSER"),
??????? CMyData(1,"isdong")
??? };
??? QuickSort(data,8);
??? for (int i=0;i<8;i++)
??????? cout<<data[i].m_iIndex<<"? "<<data[i].GetData()<<"/n";
??? cout<<"/n";
}
?
轉載聲明： 本文轉自 http://lxh1155.blog.163.com/blog/static/9311430200992113625652/
?
==============================================================================
?
各種排序算法總結
?
一、選擇排序
1. 基本思想：
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。
2. 排序過程：
【示例】：
?? 初始關鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序結果 13 27 38 49 49 76 76 97
3.
void selectionSort(Type* arr,long len)
{
?? long i=0,j=0;/*iterator value*/
?? long maxPos;
?? assertF(arr!=NULL,"In InsertSort sort,arr is NULL/n");
?? for(i=len-1;i>=1;i--)
?? {
???????????? maxPos=i;
???????????? for(j=0;j<i;j++)
????????????????? if(arr[maxPos]<arr[j])maxPos=j;
???????????? if(maxPos!=i)swapArrData(arr,maxPos,i);
?? }
}
選擇排序法的第一層循環從起始元素開始選到倒數第二個元素,主要是在每次進入的第二層循環之前,將外層循環的下標賦值給臨時變量,接下來的第二層循環中,如果發現有比這個最小位置處的元素更小的元素,則將那個更小的元素的下標賦給臨時變量,最后,在二層循環退出后,如果臨時變量改變,則說明,有比當前外層循環位置更小的元素,需要將這兩個元素交換.
二.直接插入排序
插入排序（Insertion Sort）的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。
直接插入排序
直接插入排序（Straight Insertion Sort）：將一個記錄插入到排好序的有序表中，從而得到一個新的、記錄數增1的有序表。
直接插入排序算法
哨兵（監視哨）有兩個作用：一是作為臨變量存放R[i]（當前要進行比較的關鍵字）的副本；二是在查找循環中用來監視下標變量j是否越界。
當文件的初始狀態不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態為正序，此時算法的時間復雜度為O(n)，最壞情況是文件初態為反序，相應的時間復雜度為O(n2)，算法的平均時間復雜度是O(n2)。算法的輔助空間復雜度是O(1)，是一個就地排序。
直接插入排序是穩定的排序方法。
三. 冒泡排序
[算法思想]：將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。
?
??? [算法]：
???? void BubbleSort(SeqList R) {
???? //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序
???????? int i，j；
???????? Boolean exchange； //交換標志
???????? for(i=1;i<n;i++){ //最多做n-1趟排序
???????????? exchange=FALSE； //本趟排序開始前，交換標志應為假
???????????? for(j=n-1;j>=i；j--) //對當前無序區R[i..n]自下向上掃描
???????????????? if(R[j+1].key<R[j].key){//交換記錄
???????????????????? R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元
???????????????????? R[j+1]=R[j]；
???????????????????? R[j]=R[0]；
???????????????????? exchange=TRUE； //發生了交換，故將交換標志置為真
???????????????? }
???????????? if(!exchange) return；//本趟排序未發生交換，提前終止算法
???????? } //endfor(外循環)
???? } //BubbleSort
??? [分析]：起泡排序的結束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。 [算法思想]：將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。
?
??? [算法]：
???? void BubbleSort(SeqList R) {
???? //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序
???????? int i，j；
???????? Boolean exchange； //交換標志
???????? for(i=1;i<n;i++){ //最多做n-1趟排序
???????????? exchange=FALSE； //本趟排序開始前，交換標志應為假
???????????? for(j=n-1;j>=i；j--) //對當前無序區R[i..n]自下向上掃描
???????????????? if(R[j+1].key<R[j].key){//交換記錄
???????????????????? R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元
???????????????????? R[j+1]=R[j]；
???????????????????? R[j]=R[0]；
???????????????????? exchange=TRUE； //發生了交換，故將交換標志置為真
???????????????? }
???????????? if(!exchange) return；//本趟排序未發生交換，提前終止算法
???????? } //endfor(外循環)
???? } //BubbleSort
??? [分析]：起泡排序的結束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。
四. 希爾排序
基本思想：
??? 先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
??? 該方法實質上是一種分組插入方法。
給定實例的shell排序的排序過程
??? 假設待排序文件有10個記錄，其關鍵字分別是：
??????? 49，38，65，97，76，13，27，49，55，04。
??? 增量序列的取值依次為：
??????? 5，3，1
Shell排序的算法實現
1． 不設監視哨的算法描述
void ShellPass(SeqList R，int d)
?? {//希爾排序中的一趟排序，d為當前增量
???? for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當前的有序區
?????? if(R[i].key<R[i-d].key){
???????? R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵
???????? do {//查找R[i]的插入位置
??????????? R[j+d]；=R[j]； //后移記錄
??????????? j=j-d； //查找前一記錄
???????? }while(j>0&&R[0].key<R[j].key)；
???????? R[j+d]=R[0]； //插入R[i]到正確的位置上
?????? } //endif
?? } //ShellPass
void ShellSort(SeqList R)
?? {
??? int increment=n； //增量初值，不妨設n>0
??? do {
????????? increment=increment/3+1； //求下一增量
????????? ShellPass(R，increment)； //一趟增量為increment的Shell插入排序
?????? }while(increment>1)
??? } //ShellSort
注意：
??? 當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內循環中增加了一個循環判定條件"j>0"，以防下標越界。
2．設監視哨的shell排序算法
算法分析
1．增量序列的選擇
??? Shell排序的執行時間依賴于增量序列。
??? 好的增量序列的共同特征：
?、?最后一個增量必須為1；
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
??? 有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6n1.25之間。
2．Shell排序的時間性能優于直接插入排序
??? 希爾排序的時間性能優于直接插入排序的原因：
?、佼斘募鯌B基本有序時直接插入排序所需的比較和移動次數均較少。
②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。
?、墼谙柵判蜷_始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。
??? 因此，希爾排序在效率上較直接插人排序有較大的改進。
3．穩定性
??? 希爾排序是不穩定的。參見上述實例，該例中兩個相同關鍵字49在排序前后的相對次序發生了變化。
五. 堆排序
1、 堆排序定義
??? n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
??? (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤? )
??? 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。
【例】關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
??? 根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。
??? 根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
注意：
??? ?、俣阎腥我蛔訕湟嗍嵌选?br />
??? ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
3、堆排序特點
??? 堆排序(HeapSort)是一樹形選擇排序。
??? 堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系【參見二叉樹的順序存儲結構】，在當前無序區中選擇關鍵字最大(或最小)的記錄。
4、堆排序與直接插入排序的區別
??? 直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由于前一趟排序時未保留這些比較結果，所以后一趟排序時又重復執行了這些比較操作。
??? 堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
?
5、堆排序
??? 堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最后一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
??? ……
直到無序區只有一個元素為止。
（2）大根堆排序算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最后一個記錄交換，然后將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由后往前逐步擴大至整個向量為止。
（3）堆排序的算法：
void HeapSort(SeqIAst R)
?? { //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
??? int i；
??? BuildHeap(R)； //將R[1-n]建成初始堆
??? for(i=n;i>1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
????? R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最后一個記錄交換
??? Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質
???? } //endfor
?? } //HeapSort
（4） BuildHeap和Heapify函數的實現
因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。
① Heapify函數思想方法
每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換后，新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其余任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。
"篩選法"調整堆
R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小于這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結點R[large]違反堆性質，同樣由于該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。
②BuildHeap的實現
要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。
顯然只有一個結點的樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ，? -1，…，1的結點作為根的子樹都調整為堆即可。
??? 具體算法【參見教材】。
5、大根堆排序實例
??? 對于關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見。
6、 算法分析
??? 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
?? 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。
??? 由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。
??? 堆排序是就地排序，輔助空間為O(1)，
??? 它是不穩定的排序方法。
六. 快速排序
快速排序的基本思路是：首先我們選擇一個中間值middle（程序中我們可使用數組中間值），把比中間值小的放在其左邊，比中間值大的放在其右邊。由于這個排序算法較復雜，我們先給出其進行一次排序的程序框架（從各類數據結構教材中可得）：
void QuickSort(int *pData, int left, int right)
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中間值
do
{
while ((pData[i] < middle) && (i < right)) //從左掃描大于中值的數
i++;
while ((pData[j] > middle) && (j > left)) //從右掃描小于中值的數
j--;
if (i <= j) //找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j) ; //如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left<j)
QuickSort (pData,left,j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right>i)
QuickSort (pData,i,right);
}
對于n個成員，快速排序法的比較次數大約為n*logn 次，交換次數大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950 次比較，而快速排序法僅需要200 次，快速排序法的效率的確很高。快速排序法的性能與中間值的選定關系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降?？焖倥判蛩惴ㄗ顗那闆r下的時間復雜度為O(n2)，而平均時間復雜度為O(n*logn)。
七. 合并排序
說明
之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？
解法
可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。
有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。
那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數字不斷的分為兩個等分，直到最後剩一個數字為止，然後再反過來不斷的合併，就如下圖所示：
?
不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。
下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。
例子
?
C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX1 10
#define MAX2 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
int partition(int[], int, int);
void quicksort(int[], int, int);
void mergesort(int[], int, int[], int, int[]);
int main(void) {
int number1[MAX1] = {0};
int number2[MAX1] = {0};
int number3[MAX1+MAX2] = {0};
int i, num;
srand(time(NULL));
printf("排序前：");
printf("/nnumber1[]：");
for(i = 0; i < MAX1; i++) {
number1[i] = rand() % 100;
printf("%d ", number1[i]);
}
printf("/nnumber2[]：");
for(i = 0; i < MAX2; i++) {
number2[i] = rand() % 100;
printf("%d ", number2[i]);
}
// 先排序兩筆資料
quicksort(number1, 0, MAX1-1);
quicksort(number2, 0, MAX2-1);
printf("/n排序後：");
printf("/nnumber1[]：");
for(i = 0; i < MAX1; i++)
printf("%d ", number1[i]);
printf("/nnumber2[]：");
for(i = 0; i < MAX2; i++)
printf("%d ", number2[i]);
// 合併排序
mergesort(number1, MAX1, number2, MAX2, number3);
printf("/n合併後：");
for(i = 0; i < MAX1+MAX2; i++)
printf("%d ", number3[i]);
printf("/n");
return 0;
}
int partition(int number[], int left, int right) {
int i, j, s;
s = number[right];
i = left - 1;
for(j = left; j < right; j++) {
if(number[j] <= s) {
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i+1;
}
void quicksort(int number[], int left, int right) {
int q;
if(left < right) {
q = partition(number, left, right);
quicksort(number, left, q-1);
quicksort(number, q+1, right);
}
}
void mergesort(int number1[], int M, int number2[],
int N, int number3[]) {
int i = 0, j = 0, k = 0;
while(i < M && j < N) {
if(number1[i] <= number2[j])
number3[k++] = number1[i++];
else
number3[k++] = number2[j++];
}
while(i < M)
number3[k++] = number1[i++];
while(j < N)
number3[k++] = number2[j++];
}
?
Java
?
public class MergeSort {
public static int[] sort(int[] number1,
int[] number2) {
int[] number3 =
new int[number1.length + number2.length];
int i = 0, j = 0, k = 0;
while(i < number1.length && j < number2.length) {
if(number1[i] <= number2[j])
number3[k++] = number1[i++];
else
number3[k++] = number2[j++];
}
while(i < number1.length)
number3[k++] = number1[i++];
while(j < number2.length)
number3[k++] = number2[j++];
return number3;
}
}
八?；鶖蹬判?br />
基數排序是根據組成關鍵字的各位值，用"分配"和"收集"的方法進行排序。例如，把撲克牌的排序看成由花色和面值兩個數據項組成的主關鍵字排序。
花色：梅花<方塊<紅心<黑桃
面值：2<3<4<...<10<J<Q<K<A
若要將一副撲克牌排成下列次序：
梅花2,...,梅花A,方塊2,...,方塊A,紅心2,...,紅心A,黑桃2,...,黑桃A。
有兩種排序方法：
一、先按花色分成四堆，把各堆收集起來；然后對每堆按面值由小到大排列，再按花色從小到大按堆收疊起來。----稱為"最高位優先"(MSD)法。
二、先按面值由小到大排列成13堆,然后從小到大收集起來；再按花色不同分成四堆,最后順序收集起來。----稱為"最低位優先"(LSD)法。
[例] 設記錄鍵值序列為{88,71,60,31,87,35,56,18}，用基數排序(LSD)。如圖所示：其中f[i]、e[i]為按位分配面值為i的隊列的隊頭和隊尾指針。
?? #define D 3
?? typedef struct
?? { int key;
???? float data;
???? int link;
?? } JD
?key??? data??? link
int jspx(JD r[],int n)
{ /*鏈式存儲表示的基數排序*/
?? int i,j,k,t,p,rd,rg,f[10],e[10];
?? /*p為r[]的下標,rd,rg為比例因子,f[j],e[j]是代碼為j的隊的首尾指針*/
?? for(i=1;i<n;i++) r[i].link=i+1;
?? r[n].link=0;
?? p=1;rd=1;rg=10;
?? for(i=1;i<=D;i++)
?? { for(j=0;j<10;j++) { f[j]=0;e[j]=0; } /*各隊列初始化*/
???? do /*按位分配--分到各隊列中*/
???? { k=(r[p].key%rg)/rd; /*取鍵值的某一位*/
?????? if(f[k]==0) f[k]=p;
?????? else r[e[k]].link=p; /*有重復值--修改鏈接*/
?????? e[k]=p;
?????? p=r[p].link; /*取下一個結點的地址*/
???? }while(p>0);
???? j=0; /*按位收集--調整分配后的鏈接*/
???? while(f[j]==0) j=j+1;
???? p=f[j];t=e[j];
???? for(k=j+1;k<10;k++)
?????? if(f[k]>0){ r[t].link=f[k];t=e[k]; }/*調整鏈接*/
???? r[t].link=0; /*鏈尾為0*/
???? rg=rg*10;rd=rd*10; /*提高一位*/
?? }
?? return(p); /*返回有序鏈表的首地址*/
九 枚舉排序
將每個記錄項與其他諸項比較計算出小于該項的記錄個數，以確定該項的位置。
?
轉載聲明： 本文轉自 http://student.csdn.net/space.php?uid=49357&do=blog&id=11377
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的各种排序算法及其实现总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 委派用户管理Hyper-v
- 下一篇： linux中的变量文件路径,Linux库