八、排序 | 數據結構

一、基本概念

1、排序：將一組「無序」的記錄序列調整為「有序」的記錄序列。

2、穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序後的序列中，ri仍在rj之前，則稱這種排序演算法是穩定的；否則稱為不穩定的。

3、排序演算法的分類：插入類、交換類、選擇類、歸併類和基數類。

二、插入類排序

1、直接插入排序

複雜度：O(n^2)

插入排序和人們打牌時抽牌所用的排序方式類似：

1、抽第一張牌，此時手上的牌只有一張，所以是有序的。

2、再抽一張牌，和手上的那張牌的大小進行比較，比它大就放在後面，否則放在前面。

3、再抽一張牌，和手上的牌進行比較，找到合適的位置插入，保持手上的牌有序。

4、不斷重複3，直到牌抽完。

void insertSort(int arr[],int n){ for(int i=1;i<n;i++){ int insertPos=i,item=arr[i]; for(int j=0;j<i;j++){//尋找合適的插入位置O(N) if(arr[i]<arr[j]){ insertPos=j; break; } } for(int j=i;j>insertPos;j--){//調整元素位置後插入 arr[j]=arr[j-1]; } arr[insertPos]=item; }}void InsertSort(int arr[],long size){//邊尋找合適的插入位置邊調整元素位置 for(int i=1;i<size;i++){ int temp=arr[i];//保存需要插入的元素 int j=i-1; while(j>=0){//尋找合適的插入位置 if(temp<arr[j])arr[j+1]=arr[j];//如果當前元素較需要插入的元素小，調整該元素的位置 else break;//否則已找到合適的位置，退出循環 j--; } arr[j+1]=temp;//在合適的位置插入元素 }}

2、折半插入排序

和直接插入排序唯一不同之處在於，第三步尋找合適位置時採用折半查找的方式進行查找，這將尋找插入位置的複雜度由O(N)減少為O(lgN)，但由於調整元素位置的時間仍然為O(N)，所以演算法的整體複雜度仍然為O(N^2)。

void BinaryInsertSort(int arr[],long size){ for(int i=1;i<size;i++){ int temp=arr[i];//保存需要插入的元素 int lo=0,hi=i; while(lo<hi){//二分查找插入位置 int mi=lo+((hi-lo)>>1); if(temp<arr[mi])hi=mi; else lo=mi+1; } for(int j=i;j>lo;j--){//調整元素位置後插入 arr[j]=arr[j-1]; } arr[lo]=temp; }}

3、希爾排序

希爾排序本質上是分組的插入排序。分組有什麼好處呢？因為插入排序的複雜度為O(N^2)，如果將N個元素分為k組，每一次分組的演算法的複雜度就變成了1/k^2*O(N^2)，大大減少了運算量。

void ShellSort(int arr[],int n){ int h=1;//interval while(h<n/2)h=h*3+1; while(h>=1){//裡面是一個插入排序演算法 for(int i=h;i<n;i++){ for(int j=i;j>=h&&arr[j]<arr[j-h];j-=h) swap(arr[j-h],arr[j]); } h/=3; }}void ShellSort2(int arr[],int n){//更快的希爾排序 int h=1;//interval while(h<n/3)h=h*3+1; while(h>=1){//裡面是一個插入排序演算法 for(int i=h;i<n;i++){ int temp=arr[i]; int j=i-h; while(j>=0){ if(temp<arr[j])arr[j+h]=arr[j]; else break; j-=h; } arr[j+h]=temp; } h/=3; }}

二、交換類排序

1、冒泡排序

複雜度：O(n^2)

1、對數組array[n]進行從0~n-1項的掃描，每碰到相鄰兩項數值大的在前小的在後時，對二者進行交換。當掃描進行完成後，0~n-1中最大的元素必然已經在array[n-1]就位，而所有數值較小，序號卻靠後的元素，序號也減小了1。

2、既然最大的元素已在array[n-1]的位置就位，接下來的掃描只需從0~n-2。具體過程同1。同樣的，掃描結束後0~n-2中最大的元素（全數組第二大的元素）必然已經在array[n-2]就位，而所有數值較小，序號卻靠後的元素，序號也減小了1。

3、如此不斷重複，直到最小的元素在array[0]的位置就位。

void BubbleSort(int a[],long size){ for(long i=0;i<size;i++){ bool flag=true;//標記，如果在下次循環中，沒有出現位置交換，說明排序已完成 for(long j=0;j<size-i-1;j++){//每循環一次，最大的元素會就位一個 if(a[j]>a[j+1]){ swap(a[j+1],a[j]); flag=false; } } if(true==flag)return; }}

2、快速排序

複雜度：O(n^2) （最壞情況）O(nlogn)（平均情況）

1、從數組中隨機選出一個元素，和數組首元素互換位置，並記下其大小。

2、使用兩個指針，指針a指向數組頭，指針b指向數組尾。

3、指針b從後向前掃描，找到一個數比選出元素小時，暫停，將其值保存在指針a所指的位置中。

4、指針a從前往後掃描，找到一個數比選出元素大時，暫停，將其值保存在指針b所指的位置中。

5、循環重複3、4，直到a<b不再成立。

6、將選出元素放在指針a、b同時指向的位置，並用此位置將數組分割成前後不包含選出元素的兩個子數組，對子數組進行步驟1~6。

void QuickSort(int arr[],int lo,int hi){ if(hi-lo<2)return;//如果分段中的元素小於兩個，就沒必要進行比較了 int pivot=rand()%(hi-lo)+lo;//利用隨機數確定一個軸點 int key=arr[pivot];//保存軸點元素的備份 swap(arr[lo],arr[pivot]); int l=lo,r=hi-1; while(l<r){//l==r時為循環退出的條件 while(l<r&&key<=arr[r])r--; arr[l]=arr[r]; while(l<r&&arr[l]<=key)l++; arr[r]=arr[l]; } arr[l]=key;//此時的l即為軸點應該處於的位置 QuickSort(arr, lo, l);//分治，對子數組進行同樣的處理 QuickSort(arr, l+1, hi);//分治，對子數組進行同樣的處理}

三、選擇類排序

1、選擇排序

複雜度：O(n^2)

1、從數組中找出最小的元素，找出來後，將其和數組首元素互換位置。

2、此時待排序的數組規模-1。對這個規模減小的數組進行步驟1、直到待排序的數組規模為0。

void SelectSort(int arr[],long size){ for(long i=size-1;i>=0;i--){//從數組尾開始 int maxnum=arr[i]; long rank=i; for(long j=0;j<i;j++){//選出最大的元素 if(arr[j]>=maxnum){ maxnum=arr[j]; rank=j; } } swap(arr[rank], arr[i]);//放在數組無序部分中的末端 }}

2、堆排序

複雜度：O(nlgn)

將所有元素放入優先隊列中，優先隊列總彈出優先順序最高（最大、最小等）的元素，利用這個特性即可實現一個十分簡單的排序演算法。

void HeapSort(int arr[],int n){ PQ q(n);//優先隊列 for(int i=0;i<n;i++)q.insert(arr[i]); for(int i=0;i<n;i++)arr[i]=q.pop();}

具體的優先隊列實現代碼參考：手把手教你實現一個優先隊列

四、二路歸併排序

歸併排序

複雜度：O(nlogn)

歸併排序（自頂向下）的操作有兩步，分割和歸併

1、分割：將數組二等分，並將得到的子數組繼續二等分，直到每個子數組只剩下一個元素為止。

2、歸併：不斷將原本屬於同一個數組的兩個子數組歸併成一個有序的數組，方法為不斷比較子數組的首元素，並彈出較小的放入合併後組成的數組中。直到所有子數組合併為一個數組。

自底向上的歸併排序在第一步上有差別，它直接從最小的數組（只含一個元素）開始合併。

分割（自頂向下）：

void MergeSort(int arr[],int lo,int hi){//自頂向下遞歸，採用merge if(hi-lo<2)return; int mi=(lo+hi)/2; MergeSort(arr,lo, mi); MergeSort(arr,mi, hi); Merge(arr,lo,mi,hi);}

分割（自底向上）：

void MergeSortDownToUp(int arr[],int n){//自底向上迭代 for(int sz=1;sz<n;sz<<=1){//歸併段大小 for(int l=0;l+sz<n;l+=sz+sz){//一段段地歸併 Merge(arr, l, l+sz, min(l+2*sz,n)); } }}

歸併：

void Merge(int arr[],int lo,int mi,int hi){//合併方法一 int ml=mi-lo; int *b=new int[ml]; for(int i=0;i<ml;i++)b[i]=arr[i+lo];//備份兩段中的前段，注意要從lo開始 int x=0,y=mi; for(int i=lo;i<hi;){ if(y>=hi||(x<ml&&b[x]<=arr[y]))//如果後段越界或者前段未越界且小於後段 arr[i++]=b[x++]; if(x>=ml||(y<hi&&arr[y]<b[x]))//如果前段越界或者後段未越界且小於前段 arr[i++]=arr[y++]; } delete []b;}

void Merge2(int arr[],int lo,int mi,int hi){//合併方法二，代碼更易懂，速度稍慢 int ml=mi-lo; int *b=new int[ml]; for(int i=0;i<ml;i++)b[i]=arr[i+lo];//備份兩段中的前段，注意要從lo開始 int x=0,y=mi; for(int i=lo;i<hi;i++){ if(x>=ml)arr[i]=arr[y++];//如果前段越界 else if(y>=hi)arr[i]=b[x++];//如果後段越界 else if(b[x]<=arr[y])arr[i]=b[x++];//如果前段未越界且比後段小 else arr[i]=arr[y++]; } delete []b;}

更詳細的介紹以及速度測試參考：完全理解歸併排序

五、基數排序

基數排序

複雜度：O(n)

和string排序的思想相同。從權重最小的數位開始,依據其數位上的數從0~9排序，直到權重最高的數位排序完畢，數組也就有序了。

int Maxbit(int arr[],long size){//求最高位數 int maxnum=0; for(int i=0;i<size;i++) if(arr[i]>maxnum)maxnum=arr[i]; int bit=0; while(maxnum){ maxnum/=10; bit++; } return bit;}void RadixSort(int arr[],long size){//基數排序 int bit=Maxbit(arr, size);//求最高位數 int radix=1; int *tmp=new int[size];// int *countn=new int[10];//用於統計某一位數字為0~9的數字的數量分別是多少 while(bit--){// for(int i=0;i<10;i++)countn[i]=0;//初始化統計位 for(int i=0;i<size;i++){ int k=(arr[i]/radix)%10;//依據特定數位的上的數進行統計 countn[k]++; } for(int i=1;i<10;i++)countn[i]+=countn[i-1];//得出某數位為0~9在數組中的分割位置 for(int i=0;i<size;i++){//依據數位將數組重新排布 int k=(arr[i]/radix)%10; tmp[countn[k]-1]=arr[i]; countn[k]--; } for(int i=0;i<size;i++)arr[i]=tmp[i];//將重排後的數組導回原數組 radix*=10; }//排序完成，善後工作 delete []tmp; tmp=NULL; delete []countn; countn=NULL;}

六、外部排序

1、概念與流程

1、用普通的排序演算法將n個元素變成k個有序段

2、將k段分成m組

3、使用多路歸併排序將m個有序段變成一個有序段，有序段的數量由k變成[k/m]（向上取整）

4、重複2、3直到有序段的數量變成1。

2、多路並歸的代碼實現

前置知識點：演算法優化小助手：索引優先隊列

#include<iostream>#include<vector>#include <climits>using namespace std;#define maxn (1<<10)class indexPQ{private: int *pq;//二叉堆，維護一個優先隊列指針 int *qp;//二叉堆的逆序，pq[qp[i]]=qp[pq[i]]=i; int *key;//保存元素 int sz;// int capacity;//索引優先隊列public: indexPQ(int n){ pq=new int [n+1];//pq[0]不使用 qp=new int [n+1];//qp[0]不使用 for(int i=1;i<=n;i++)qp[i]=-1;//qp[i]=-1表示索引優先隊列i處為空 key=new int [n+1];//qp[0]不使用 sz=0; capacity=n; } ~indexPQ(){ delete []pq; delete []qp; delete []key; } int operator[](int n){ return key[n]; } bool insert(int k ,int val){//在第k個位置將key插入優先隊列,複雜度O(lgN) if(k>capacity)return false; sz++; pq[sz]=k;//第sz個插入索引優先隊列的元素在位置k qp[k]=sz;//位置k是第sz個插入索引優先隊列的元素 key[k]=val;//在位置k保存元素值 swim(sz);//將第sz個插入索引優先隊列的元素放置到堆中合適的位置 return true; } void pop(){ if(sz>0){ exch(1, sz--);//sz要在sink前減少 sink(1); key[pq[sz+1]]=NULL; qp[pq[sz+1]]=-1; } } bool contain(int k){//位置是否存在元素 return qp[k]!=-1; } int top(){ return key[pq[1]]; } int topIndex(){ return pq[1]; } void change(int k,int val){ if(-1==qp[k])insert(k, val); key[k]=val; swim(qp[k]);//將二叉堆中k對應的元素進行上浮下沉處理 sink(qp[k]); } void del(int k){ int index=qp[k]; exch(index,sz--); swim(index); sink(index); key[k]=NULL; qp[k]=-1; } bool empty(){ return sz==0; } int size(){ return sz; } //for test void print(){ for(int i=1;i<=sz;i++)cout<<i<< <<pq[i]<<": "<<key[pq[i]]<<endl; } bool check(){ for(int i=sz;i>=1;i--){ if(i/2>=1){ if(cmp(key[pq[i]],key[pq[i>>1]])){ cout<<"Problem here: "<<qp[i]<< <<pq[i]<<": "<<key[pq[i]]<< <<pq[i>>1]<<": "<<key[pq[i>>1]]<<endl; return false; } } } return true; }private: bool cmp(int a,int b){ return a<b; } void swim(int n){//演算法複雜度O(lgN) while(n>1&&cmp(key[pq[n]],key[pq[n>>1]])){//如果key[pq[n]]優先順序較高，則上浮 exch(n,n>>1); n>>=1; } } void sink(int n){//演算法複雜度O(lgN) while(2*n<=sz){ int k=2*n; if(k<sz&&cmp(key[pq[k+1]],key[pq[k]]))k++;//在左右孩子中選出優先順序高的一個 if(cmp(key[pq[k]],key[pq[n]])){//如果k比n優先順序高，n下沉 //cout<<"Exchange: "<<key[pq[k]]<< <<key[pq[n]]<<endl; exch(n,k); n=k; }else break; } } void exch(int a,int b){ int i=pq[a],j=pq[b]; swap(pq[a],pq[b]); swap(qp[i],qp[j]); }};void QuickSort(int arr[],int lo,int hi){ if(hi-lo<2)return;//如果分段中的元素小於兩個，就沒必要進行比較了 int pivot=rand()%(hi-lo)+lo;//利用隨機數確定一個軸點 int key=arr[pivot];//保存軸點元素的備份 swap(arr[lo],arr[pivot]); int l=lo,r=hi-1; while(l<r){//l==r時為循環退出的條件 while(l<r&&key<=arr[r])r--; arr[l]=arr[r]; while(l<r&&arr[l]<=key)l++; arr[r]=arr[l]; } arr[l]=key;//此時的l即為軸點應該處於的位置 QuickSort(arr, lo, l);//分治 QuickSort(arr, l+1, hi);//分治}void print(int a[],int size){//列印數組 for(int i=0;i<size;i++){ cout<<a[i]<<" "; if(0==i+1%4)cout<<endl; }}bool check(int arr[],int n){//檢查數組是否排序成功 for(int i=1;i<n;i++){ if(arr[i-1]>arr[i]){ cout<<"False: "<<i-1<<": "<<arr[i-1]<< <<i<<": "<<arr[i]<<endl; return false; } } cout<<"True"<<endl; return true;}int main(){ int *arr[maxn];//構造一個二維數組，即maxn個分段 for(int i=0;i<maxn;i++)arr[i]=new int[maxn];//申請內存 clock_t s,e;//用於計時 srand(unsigned(clock()));//生成隨機數 for(int i=0;i<maxn;i++)//向二維數組輸入隨機數 for(int j=0;j<maxn;j++) arr[i][j]=rand(); s=clock(); for(int i=0;i<maxn;i++)//利用快速排序對每一個分段進行排序 QuickSort(arr[i],0,maxn); int len=maxn*maxn;//合併後分段長度 int*res=new int[len];//用於保存排序好的數組 indexPQ Q(maxn);//索引優先隊列，從1開始 int*indexMark=new int[maxn];//保存指向每一段未排序頭元素的指針 for(int i=0;i<maxn;i++)indexMark[i]=0;//初始化指針 for(int i=0;i<maxn;i++)//將每一段的初始頭結點輸入索引優先隊列 Q.insert(i+1,arr[i][indexMark[i]++]); for(int i=1;i<=len;i++){//進行多路歸併 res[i-1]=Q.top();//將優先順序最高（最小）的元素放入數組 int topindex=Q.topIndex();Q.pop();//獲取剛剛那個元素所屬段的序號 if(indexMark[topindex-1]<maxn)//如果所屬段還未歸併完成 Q.insert(topindex, arr[topindex-1][indexMark[topindex-1]++]);//將後續元素補充進索引優先隊列 } e=clock(); //print(res,len);//列印結果 check(res,len); cout<<endl<<len<<" Num-Sortint "<<"MultiMergeSort Using: "<<e-s<<" us"<<endl;}

輸出：

True1048576 Num-Sortint MultiMergeSort Using: 888666 us

對1024段大小為1024的數組（一共1048576個隨機數）進行歸併排序成功，用時0.889秒。

其中大小為1024的indexPQ（索引優先隊列）就可以看做內存，利用1024個整型變數大小的內存對100萬個整型變數進行排序，這就是外部排序的意義：當數組大得內存放不下時，僅利用一小部分內存對龐大的數組進行高效地排序。

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

推薦閱讀：