root@iZ14rcmneyrcltZ:~/cpptest# ./FindAlgorithm 1000
CLOCKS_PER_SEC=1000000
ret=999求最值元素的时间复杂度O(n)求最大元素 用时 10(0.000010秒)
ret=999求最值元素的时间复杂度O(n)stl泛型算法求最大元素 用时 6(0.000006秒)
ret=999求最值元素的时间复杂度O(n)模板函数求最大元素 用时 5(0.000005秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./FindAlgorithm 10000
CLOCKS_PER_SEC=1000000
ret=9999求最值元素的时间复杂度O(n)求最大元素 用时 68(0.000068秒)
ret=9999求最值元素的时间复杂度O(n)stl泛型算法求最大元素 用时 36(0.000036秒)
ret=9999求最值元素的时间复杂度O(n)模板函数求最大元素 用时 29(0.000029秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./FindAlgorithm 100000
CLOCKS_PER_SEC=1000000
ret=99999求最值元素的时间复杂度O(n)求最大元素 用时 625(0.000625秒)
ret=99999求最值元素的时间复杂度O(n)stl泛型算法求最大元素 用时 518(0.000518秒)
ret=99999求最值元素的时间复杂度O(n)模板函数求最大元素 用时 294(0.000294秒)
结论：求最值元素的时间复杂度O(n)与程序运行结果是一致的，且stl泛型算法做了优化。
冒泡排序与快速排序在平均情况、最好情况、最坏情况下的时间复杂度：
T0_b=O(n^2),Tg_b=O(n),Tw_b=O(n^2),
T0_q=O(nlogn),Tg_q=O(nlogn),Tw_q=O(n^2),
T0_b上的点：(10,5)、(100,30)、(1000,2272)、(2000,8877)、(10000,255516)、(20000,1000825)
T0_q上的点：(10,2)、(100,10)、(1000,111)、(2000,222)、(10000,1329)、(20000,2833)
Tg_b上的点：(10,2)、(100,2)、(1000,5)、(2000,8)、(10000,38)、(20000,76)
Tg_q上的点：(10,2)、(100,19)、(1000,1499)、(2000,6023)、(10000,145172)、(20000,643908)
Tw_b上的点：(10,2)、(100,27)、(1000,2845)、(2000,8877)、(10000,272362)、(20000,1078493)
Tw_q上的点：(10,2)、(100,17)、(1000,1476)、(2000,5928)、(10000,296355)、(20000,595013)
结论：
T0_b=Tw_b=Tw_q=O(n^2)与程序运行结果是一致的，规模n增大10倍，那么运行时间增大100倍。
root@iZ14rcmneyrcltZ:~/cpptest# ./TickMeter 10
CLOCKS_PER_SEC=1000000
平均情况下冒泡排序 用时 5(0.000005秒)
平均情况下冒泡排序1 用时 3(0.000003秒)
平均情况下希尔排序 用时 2(0.000002秒)
平均情况下stl标准排序 用时 2(0.000002秒)
平均情况下快速排序 用时 2(0.000002秒)
最好情况下冒泡排序 用时 2(0.000002秒)
最好情况下冒泡排序1 用时 2(0.000002秒)
最好情况下希尔排序 用时 1(0.000001秒)
最好情况下stl标准排序 用时 2(0.000002秒)
最好情况下快速排序 用时 2(0.000002秒)
最坏情况下冒泡排序 用时 2(0.000002秒)
最坏情况下冒泡排序1 用时 2(0.000002秒)
最坏情况下希尔排序 用时 2(0.000002秒)
最坏情况下stl标准排序 用时 2(0.000002秒)
最坏情况下快速排序 用时 2(0.000002秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./TickMeter 100
CLOCKS_PER_SEC=1000000
平均情况下冒泡排序 用时 30(0.000030秒)
平均情况下冒泡排序1 用时 31(0.000031秒)
平均情况下希尔排序 用时 11(0.000011秒)
平均情况下stl标准排序 用时 15(0.000015秒)
平均情况下快速排序 用时 10(0.000010秒)
最好情况下冒泡排序 用时 2(0.000002秒)
最好情况下冒泡排序1 用时 16(0.000016秒)
最好情况下希尔排序 用时 3(0.000003秒)
最好情况下stl标准排序 用时 9(0.000009秒)
最好情况下快速排序 用时 19(0.000019秒)
最坏情况下冒泡排序 用时 27(0.000027秒)
最坏情况下冒泡排序1 用时 28(0.000028秒)
最坏情况下希尔排序 用时 6(0.000006秒)
最坏情况下stl标准排序 用时 8(0.000008秒)
最坏情况下快速排序 用时 17(0.000017秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./TickMeter 1000
CLOCKS_PER_SEC=1000000
平均情况下冒泡排序 用时 2272(0.002272秒)
平均情况下冒泡排序1 用时 2179(0.002179秒)
平均情况下希尔排序 用时 163(0.000163秒)
平均情况下stl标准排序 用时 205(0.000205秒)
平均情况下快速排序 用时 111(0.000111秒)
最好情况下冒泡排序 用时 5(0.000005秒)
最好情况下冒泡排序1 用时 1497(0.001497秒)
最好情况下希尔排序 用时 65(0.000065秒)
最好情况下stl标准排序 用时 119(0.000119秒)
最好情况下快速排序 用时 1499(0.001499秒)
最坏情况下冒泡排序 用时 2845(0.002845秒)
最坏情况下冒泡排序1 用时 2658(0.002658秒)
最坏情况下希尔排序 用时 60(0.000060秒)
最坏情况下stl标准排序 用时 92(0.000092秒)
最坏情况下快速排序 用时 1476(0.001476秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./TickMeter 2000
CLOCKS_PER_SEC=1000000
平均情况下冒泡排序 用时 8877(0.008877秒)
平均情况下冒泡排序1 用时 8392(0.008392秒)
平均情况下希尔排序 用时 378(0.000378秒)
平均情况下stl标准排序 用时 417(0.000417秒)
平均情况下快速排序 用时 222(0.000222秒)
最好情况下冒泡排序 用时 8(0.000008秒)
最好情况下冒泡排序1 用时 6252(0.006252秒)
最好情况下希尔排序 用时 145(0.000145秒)
最好情况下stl标准排序 用时 289(0.000289秒)
最好情况下快速排序 用时 6023(0.006023秒)
最坏情况下冒泡排序 用时 10211(0.010211秒)
最坏情况下冒泡排序1 用时 10724(0.010724秒)
最坏情况下希尔排序 用时 154(0.000154秒)
最坏情况下stl标准排序 用时 205(0.000205秒)
最坏情况下快速排序 用时 5928(0.005928秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./TickMeter 10000
CLOCKS_PER_SEC=1000000
平均情况下冒泡排序 用时 255516(0.255516秒)
平均情况下冒泡排序1 用时 203751(0.203751秒)
平均情况下希尔排序 用时 2498(0.002498秒)
平均情况下stl标准排序 用时 2470(0.002470秒)
平均情况下快速排序 用时 1329(0.001329秒)
最好情况下冒泡排序 用时 38(0.000038秒)
最好情况下冒泡排序1 用时 150521(0.150521秒)
最好情况下希尔排序 用时 553(0.000553秒)
最好情况下stl标准排序 用时 1456(0.001456秒)
最好情况下快速排序 用时 145172(0.145172秒)
最坏情况下冒泡排序 用时 272362(0.272362秒)
最坏情况下冒泡排序1 用时 266177(0.266177秒)
最坏情况下希尔排序 用时 764(0.000764秒)
最坏情况下stl标准排序 用时 1195(0.001195秒)
最坏情况下快速排序 用时 296355(0.296355秒)
root@iZ14rcmneyrcltZ:~/cpptest# ./TickMeter 20000
CLOCKS_PER_SEC=1000000
平均情况下冒泡排序 用时 1000825(1.000825秒)
平均情况下冒泡排序1 用时 935472(0.935472秒)
平均情况下希尔排序 用时 5446(0.005446秒)
平均情况下stl标准排序 用时 5427(0.005427秒)
平均情况下快速排序 用时 2833(0.002833秒)
最好情况下冒泡排序 用时 76(0.000076秒)
最好情况下冒泡排序1 用时 598559(0.598559秒)
最好情况下希尔排序 用时 1296(0.001296秒)
最好情况下stl标准排序 用时 3240(0.003240秒)
最好情况下快速排序 用时 643908(0.643908秒)
最坏情况下冒泡排序 用时 1078493(1.078493秒)
最坏情况下冒泡排序1 用时 1276268(1.276268秒)
最坏情况下希尔排序 用时 1837(0.001837秒)
最坏情况下stl标准排序 用时 2565(0.002565秒)
最坏情况下快速排序 用时 595013(0.595013秒)
源代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class TickMeter
{
public:
TickMeter(const char *szName);
~TickMeter();
// 微秒级的时钟周期
clock_t getTimeElapsed();
private:
clock_t clockBegin, clockEnd;
string strName;
};
TickMeter::TickMeter(const char *szName)
{
clockBegin = clock();
if(szName)strName=szName;
}
TickMeter::~TickMeter()
{
clockEnd = clock();
printf("%s 用时 %d(%f秒)\n",strName.c_str(),(clockEnd - clockBegin),(clockEnd - clockBegin)*1.0/CLOCKS_PER_SEC);
}
clock_t TickMeter::getTimeElapsed()
{
clock_tcur = clock();
return (cur - clockBegin);
}
// n个整数冒泡升序排序
void pibub(int *p,int n)
{
int m,k,j,i,d;
k=0; m=n-1;
while (k<m)
{
j=m-1; m=0;
for (i=k; i<=j; i++)
if (p[i]>p[i+1])
{
d=p[i];
p[i]=p[i+1];
p[i+1]=d;
m=i;
}
j=k+1;
k=0;
for (i=m; i>=j; i--)
if (p[i-1]>p[i])
{
d=p[i];
p[i]=p[i-1];
p[i-1]=d;
k=i;
}
}
return;
}
void pibub(int *p,int n,int ascending)//ascending=1表示升序，0表示降序
{
int temp,i,j;
if(ascending)
{
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(p[j]>p[i])//选择升序排序
{
temp=p[i];
//插入
for(int k=i;k>=j;k--)p[k]=p[k-1];
p[j]=temp;
}
}
// printf("\n");
// printf("A[i=%d]=",i);
// for(int k=0;k<n;k++)
// printf("%d",p[k]);
}
}
else
{
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1;j++)
if(p[j]<p[j+1])//选择降序
{
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}
}
void pibub1(int *p,int n)
{
pibub(p,n,1);
}
// 希尔排序
void pishl(int *p,int n)
{
int k,j,i,t;
k=n/2;
while (k>0)
{
for (j=k; j<=n-1; j++)
{
t=p[j];
i=j-k;
while ((i>=0)&&(p[i]>t))
{
p[i+k]=p[i];
i=i-k;
}
p[i+k]=t;
}
k=k/2;
}
return;
}
void stlsort(int *p,int n)
{
//sort(p,p+n);//升序排列
sort(p,p+n,less<int>());//升序排列
}
void quickSort(int *arr,int startPos, int endPos)
{
int i,j;
int ch;
ch=arr[startPos];
i=startPos;
j=endPos;
while(i<j)
{
while(arr[j]>=ch && i<j)--j;
arr[i]=arr[j];
while(arr[i]<=ch && i<j)++i;
arr[j]=arr[i];
}
arr[i]=ch;
if(i-1>startPos) quickSort(arr,startPos,i-1);
if(endPos>i+1) quickSort(arr,i+1,endPos);
}
void piqck(int *p,int n)
{
quickSort(p,0,n-1);
}
vector<int> createInputArr(int n)
{
vector<int> v(n);
for(int i=0;i<n;i++)
v[i]=rand();
return v;
}
typedef void(*pR)(int *p,int n);
pR pFunc[]={pibub,pibub1,pishl,stlsort,piqck};
const char *szName[]={"冒泡排序","冒泡排序1","希尔排序","stl标准排序","快速排序"};
void Print(const char *szName,vector<int>& tlVect)
{
return;
if(tlVect.size()>10)
return;
printf("%s容器中的元素为: ",szName);
for (int i = 0; i < tlVect.size(); i++) {
printf("%d,",tlVect[i]);
}
printf("\n");
}
int main(int argc, char *argv[])
{
if( argc < 2 )
{
printf("Usage: TickMeter n [-w][-g](eg:n=1000)\n");
return 1;
}
printf("CLOCKS_PER_SEC=%d\n",CLOCKS_PER_SEC);
int n=atoi(argv[1]);
int m=sizeof(pFunc)/sizeof(pFunc[0]);
vector<int> v0=createInputArr(n);
vector<int> vg=v0;
sort(vg.begin(),vg.end(),less<int>());//升序排列
// 快速排序在完全逆序的情况下等价于冒泡排序，这时其他方法就比它快。
vector<int> vw=v0;
sort(vw.begin(),vw.end(),greater<int>());//降序排列
vector<int> *vArr[]={&v0,&vg,&vw};
const char *szVName[]={"平均情况下","最好情况下","最坏情况下"};
Print("v0",v0);
Print("vg",vg);
Print("vw",vw);
for(int j=0;j<3;j++)
for(int i=0;i<m;i++)
{
string str=szVName[j];
str+=szName[i];
TickMeter tm(str.c_str());
vector<int> v=*vArr[j];
pFunc[i](&v[0],n);
clock_t s=tm.getTimeElapsed();
Print(str.c_str(),v);
}
return 0;
}
排序算法时间复杂度理论分析与实测
原文：https://www.cnblogs.com/Ivanhan2019/p/12758487.html
