幾種排序演算法的C++實現

一、綱要

之前寫過一篇關於幾種排序演算法的介紹：

1、冒泡排序

2、歸併排序

3、插入排序

4、選擇排序

5、基數排序

6、快速排序

Uno Whoiam：多種排序演算法的C++實現（附圖）

本次測試的幾個新的排序演算法主要是：

1、堆排序

2、希爾排序

3、插入排序（二分查找優化）

另外還請了老嘉賓：快速排序。

畢竟，對於快速排序而言，在座的各位都是垃圾。

二、幾種演算法原理的簡介

1、堆排序

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

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();}

2、希爾排序

希爾排序本質上是分組的插入排序。分組有什麼好處呢？因為插入排序的複雜度為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; }}

3、二分查找優化的插入排序

利用二分查找，將尋找插入位置的複雜度由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萬隨機數排序測試：

#include<iostream>#include<vector>#include <climits>using namespace std;#define maxn (1<<15)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++){//尋找插入位置 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;//在合適的位置插入元素 }}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; }}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; }}class PQ{//手動實現的優先隊列private: int sz;//優先隊列大小 int capacity;//優先隊列容量 int*pq;//數組保存優先隊列里的元素public: PQ(int n){//構造函數 pq=new int[n+1];//pq[0]不使用 sz=0; capacity=n; } ~PQ(){//析構函數 delete []pq; } void insert(int val){ if(sz>=capacity){//如果存儲範圍超過了capacity，則將容量擴展為二倍 int* temp=new int[capacity<<1]; for(int i=1;i<=capacity;i++){ temp[i]=pq[i]; } delete []pq; pq=temp; capacity<<=1; } sz++; pq[sz]=val; swim(sz);//將新插入的元素進行上浮操作 } int top(){//返回優先度最高的元素 return pq[1]; } int pop(){//彈出優先度最高的元素 int temp=pq[1]; swap(pq[1],pq[sz--]); sink(1); return temp; } int size(){ return sz; } bool empty(){ return sz==0; }private: bool cmp(int a,int b){ return a<b; } void swim(int n){ while(n>1&&cmp(pq[n],pq[n>>1])){//如果pq[n]比父節點的優先順序大，將其上浮 swap(pq[n],pq[n>>1]); n>>=1; } } void sink(int n){ while(2*n<=sz){ int k=2*n; if(k<sz&&cmp(pq[k+1],pq[k]))k++;//選出左右孩子中優先順序更高的那個 if(cmp(pq[k],pq[n])){//如果pq[n]的優先順序低，將其下沉 swap(pq[n],pq[k]); n=k; }else break; } }};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();}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"<<endl; return false; } } cout<<"True"<<endl; return true;}int main(){ int arr[maxn]; clock_t s,e; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); insertSort(arr ,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"insertSort Using: "<<e-s<<" us"<<endl; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); InsertSort(arr ,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"better-insertSort Using: "<<e-s<<" us"<<endl; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); BinaryInsertSort(arr ,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"BinaryInsertSort Using: "<<e-s<<" us"<<endl; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); ShellSort(arr ,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"ShellSort Using: "<<e-s<<" us"<<endl; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); ShellSort2(arr ,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"ShellSort2 Using: "<<e-s<<" us"<<endl; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); HeapSort(arr ,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"HeapSort Using: "<<e-s<<" us"<<endl; srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); QuickSort(arr ,0,maxn); e=clock(); //print(arr,maxn); check(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"QuickSort Using: "<<e-s<<" us"<<endl; //test /* int a[]={1651,16516,65,19,17,165,161,1541}; QuickSort(a ,0,8); print(a,8); */}

結果：

True32768 Num-Sortint insertSort Using: 2130344 usTrue32768 Num-Sortint better-insertSort Using: 1081579 usTrue32768 Num-Sortint BinaryInsertSort Using: 1059966 usTrue32768 Num-Sortint ShellSort Using: 13420 usTrue32768 Num-Sortint ShellSort2 Using: 8057 usTrue32768 Num-Sortint HeapSort Using: 12707 usTrue32768 Num-Sortint QuickSort Using: 6453 us

可以看到快速排序和希爾排序的速度都相當快，快速排序為最。

PS：

廣告時間啦~

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