首页 > 编程语言 >多种排序算法的效率观察

多种排序算法的效率观察

时间：2024-04-28 23:56:11浏览次数：23  
标签：10000010 10 int LL long 算法 排序 效率

注：时间的单位为毫秒，每个数据均观测三次取平均值（排除异常数据）。

时间复杂度较大的排序算法

随机数据耗时

数据规模 选择排序 冒泡排序 插入排序 猴子排序
\(10\) 0 0 0 178
\(100\) 0 0 0 -
\(10^3\) 0 0 0 -
\(10^4\) 130 124 24 -

分析

选择排序、冒泡排序、插入排序时间复杂度均为 \(O(n^2)\)​，但是插入排序的时间却比其余两者小。原因是如果插入的数字不太极端的话，每一个数插到中间就break了，上限跑不满。

顺序数据耗时

数据规模 选择排序 冒泡排序 插入排序
\(10^4\) 35 0 0

由于冒泡排序和插入排序当检测到序列已经升序时，可以直接停止算法，使得二者在第一次循环结束时就结束了。选择排序仅仅是比较了 \(\frac{n\times(n-1)}{2}\) 次大小，省去了交换两数的过程，时间得到较大减少。

逆序数据耗时

数据规模 选择排序 冒泡排序 插入排序
\(10^4\) 40 79 52

选择排序竟然反杀了冒泡和插入。也许 c++ 会这点代码给优化了，于是用C语言重新写了一遍，发现有：

数据规模 选择排序 冒泡排序 插入排序
\(10^4\) 163 165 96

这符合之前的规律。但是为什么逆序时c++会出现反常还有待讨论。

时间复杂度较小的排序算法

耗时

数据规模 归并排序 堆排序 快速排序 快速排序(std)
\(10^3\) 0 0 0 0
\(10^4\) 0 1 0 0
\(10^5\) 12 12 8 5
\(10^6\) 136 176 121 84
\(10^7\) 1703 2926 1397 904

这些算法复杂度均为 \(O(n\log n)\) ，相对于之前的 \(O(n^2)\) 算法快了不少。手写堆排序常数较大，用stl的priority_queue可以优化一下常数；stl的快速排序效率非常之高，其中一个优化是当数据范围较小的时候直接进行插入排序，而非递归进行快速排序。

顺序数据耗时

数据规模 归并排序 堆排序 快速排序 快速排序(std)
\(10^5\) 4 10 3 1
\(10^6\) 53 116 40 12
\(10^7\) 634 1297 491 176

逆序数据耗时

数据规模 归并排序 堆排序 快速排序 快速排序(std)
\(10^5\) 4 7 3 1
\(10^6\) 47 98 40 10
\(10^7\) 583 1048 501 129

我们可以发现，当数据有序时排序的速度比乱序时快。但是逆序时部分算法比顺序时快一点（目前并没有搞明白是为什么）。

复杂度与值域相关的排序算法

耗时

数据规模 值域 桶排序 基数排序
\(10^4\) \(10^4\) 0 0
\(10^4\) \(10^7/10^9\) 54 0
\(10^5\) \(10^4\) 0 2
\(10^5\) \(10^7/10^9\) 57 4
\(10^6\) \(10^4\) 2 19
\(10^6\) \(10^7/10^9\) 86 41
\(10^7\) \(10^4\) 23 254
\(10^7\) \(10^7/10^9\) 344 483

由于开 \(10^9\) 个变量需要一个超大的内存，故桶排序的较大值域设为 \(10^7\)。

相关代码

选择排序

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
mt19937 mt(123456);
void xzsort()
{
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
		if(a[i]>a[j])
			swap(a[i],a[j]);
}
int main()
{
	n=10000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	// sort(a+1,a+1+n);
	// reverse(a+1,a+1+n);
	int abc=clock();
	xzsort();
	cout<<clock()-abc<<'\n';
}

冒泡排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
int a[10010];
mt19937 mt(123456);
void mpsort()
{
	for(int i=1;i<=n;i++){
		bool flag=0;
		for(int j=1;j<=n-i;j++)
		if(a[j]>a[j+1])
			swap(a[j+1],a[j]),flag=1;
		if(!flag)break;
	}
}
int main()
{
	n=10000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int abc=clock();
	mpsort();
	cout<<clock()-abc<<'\n';
}

插入排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
LL a[10010],b[10010];
mt19937 mt(123456);
void mpsort()
{
	for(int i=1;i<=n;i++){
		b[i]=a[i];
		for(int j=i;j>1;j--)
		if(a[j]<a[j-1])
			swap(a[j],a[j-1]);
		else break;
	}
	memcpy(a,b,sizeof(LL)*(n+3));
}
int main()
{
	n=10000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int abc=clock();
	mpsort();
	cout<<clock()-abc<<'\n';
}

归并排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
LL a[10000010],b[10000010];
mt19937 mt(123456);
void mergesort(int L,int R)
{
	if(L==R)return;
	int M=(L+R)>>1;
	mergesort(L,M);
	mergesort(M+1,R);
	int Lp=L,Rp=M+1,pos=L;
	while(Lp<=M||Rp<=R){
		if((a[Lp]<=a[Rp]&&Lp<=M)||Rp>R)
			b[pos++]=a[Lp++];
		else b[pos++]=a[Rp++];
	}
	memcpy(a+L,b+L,sizeof(LL)*(R-L+1));
}
int main()
{
	n=10000000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int abc=clock();
	mergesort(1,n);
	cout<<clock()-abc<<'\n';
}

堆排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
LL a[10000010],DUI[10000010],NUM;
mt19937 mt(123456);
void UP(int x)
{
	while(x>1){
		if(DUI[x]<=DUI[x>>1])return;
		DUI[x]^=DUI[x>>1]^=DUI[x]^=DUI[x>>1];
		x>>=1;
	}
}
void DOWN(int x)
{
	int y=x<<1;
	while(y<=NUM){
		if(y<NUM&&DUI[y+1]>DUI[y])
			y++;
		if(DUI[x]>=DUI[y])return;
		DUI[x]^=DUI[y]^=DUI[x]^=DUI[y];
		x=y;y<<=1;
	}
}
void ADD(LL x)
{
	DUI[++NUM]=x;
	UP(NUM);
}
void DEL()
{
	DUI[1]=DUI[NUM--];
	DOWN(1);
}
void duisort(LL A[],int Len)
{
	NUM=0;
	for(int i=1;i<=Len;i++)
		ADD(A[i]);
	for(int i=Len;i;i--)
		A[i]=DUI[1],DEL();
}
int main()
{
	n=10000000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int abc=clock();
	duisort(a,n);
	cout<<clock()-abc<<'\n';
}

快速排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int bit[4]={0,16,32,48},U=65535;
LL n,a[10000010],Maxa[10000010],Mina[10000010];
int st[66000];
mt19937 mt(123456);
void qsort(int L,int R)
{
	if(L>=R)return;
	int M=(L+R)>>1,Lp=0,Rp=0;
	LL Max=max(a[M],max(a[L],a[R])),Min=min(a[M],min(a[L],a[R]));
	LL temp=a[M]^a[L]^a[R]^Max^Min;
	for(int i=L;i<=R;i++)
	if(a[i]<temp)Mina[++Lp]=a[i];
	else if(a[i]>temp)Maxa[++Rp]=a[i];
	memcpy(a+L,Mina+1,sizeof(LL)*Lp);
	fill(a+L+Lp,a+R-Rp,temp);
	memcpy(a+R-Rp+1,Maxa+1,sizeof(LL)*Rp);
	qsort(L,L+Lp-1);
	qsort(R-Rp+1,R);
}
int main()
{
	n=10000000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int abc=clock();
	qsort(1,n);
	cout<<clock()-abc<<'\n';
}

快速排序std

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
LL a[10000010];
mt19937 mt(123456);
int main()
{
	n=10000000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%1000000000ll;
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	int abc=clock();
	sort(a+1,a+1+n);
	cout<<clock()-abc<<'\n';
}

基数排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int bit[4]={0,16,32,48},U=65535;
LL n,a[10000010],b[10000010];
int st[66000];
mt19937 mt(123456);
void radixsort()
{
	for(int d=0;d<2;++d){
		memset(st,0,sizeof st);
		for(int i=1;i<=n;++st[(a[i++]>>bit[d])&U]);
		for(int i=1;i<=U;++i)st[i]+=st[i-1];
		for(int i=n;i>0;--i)b[st[(a[i]>>bit[d])&U]--]=a[i];
		memcpy(a,b,sizeof(LL)*(n+5));
	}
}
int main()
{
	n=1000000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%10000ll;
	int abc=clock();
	radixsort();
	cout<<clock()-abc<<'\n';
}

桶排序

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,a[10000010],c[10000010];
LL b[10000010];
int st[66000];
mt19937 mt(123456);
void tongsort()
{
	for(int i=1;i<=n;++b[a[i++]]);
	for(int i=n=0;i<=10000;i++)
	while(b[i]--)a[++n]=i;
}
int main()
{
	n=100000;
	for(int i=1;i<=n;++i)
		a[i]=mt()%10000;
	int abc=clock();
	tongsort();
	cout<<clock()-abc<<'\n';
}

标签：10000010,10,int,LL,long,算法,排序,效率
From： https://www.cnblogs.com/zYzYzYzYz/p/18164782

相关文章

  • 说说你对贪心算法、回溯算法的理解？应用场景？
    一、贪心算法贪心算法，又称贪婪算法，是算法设计中的一种思想其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的举个零钱兑换的例子，如果你有1元、2元、5元的钱币数张，用于兑换一定的金额，但是要求兑换的钱币张数最少如果现在你要兑换11元，按照贪心算法......
  • 38天【代码随想录算法训练营34期】第九章 动态规划part01 （● 理论基础 ● 509. 斐波
    理论基础斐波那契数classSolution:deffib(self,n:int)->int:ifn==0:return0ifn==1:return1returnself.fib(n-1)+self.fib(n-2)爬楼梯classSolution:defclimbStairs(self,n:int)->i......
  • QJsonArray对其对象排序
    #include<QCoreApplication>#include<QJsonArray>#include<QJsonObject>#include<QDebug>#include<QList>//比较函数，用于指定排序规则boolcompareJsonObjects(constQJsonObject&obj1,constQJsonObject&obj2){returnobj1......
  • 基于FBG传感器的形状重建算法仿真
    算法涉及基本的[[FBG传感器模型]]，一般通过刻有若干个布拉格光栅的光纤集成到被测物体上，当光纤与被测物体同时发生形变的时候，布拉格光栅产生应变，从而产生波长的漂移，通过对入射光与反射光波长漂移的检测，可以计算得到光纤上若干个点的曲率与挠率。在微分几何中，可以通过[[Frenet–S......
  • python将图片添加到视频底层中（提高处理单个视频的效率）
    代码： importcv2importnumpyasnpimportosimportrandomfromconcurrent.futuresimportThreadPoolExecutor#图片文件夹路径image_folder_path=r'F:\jingguan\tu'#视频文件所在的文件夹路径video_folder_path=r'F:\jingguan\yuan'#输出视频文件夹路径ou......
  • 支持向量机的算法原理与Python实现
    支持向量机（SupportVectorMachine，SVM）是一种强大的监督学习算法，用于分类和回归任务。其核心思想是在高维空间中找到一个最优的超平面，将不同类别的数据分开。SVM的关键在于找到支持向量，即离超平面最近的数据点，这些支持向量决定了超平面的位置和方向。SVM通过最大化支持向量与超平面......
  • 算法学习笔记（14）：区间最值操作和历史最值问题
    区间最值操作,历史最值问题来源吉老师2016集训队论文，oiwiki，网络上各种博客。概述区间最值操作指的是：将所有的$i\in$\((l,r)\)，\(a_i=min或max(a_i,k)\)。历史最值问题指的是:新定义一个数组\(b[]\)，\(b[i]=max或min(b[i],a[i])\)。还有一种是历史版本和，即\(......
  • 在电脑桌面上制作可视化进度日程待办清单,效率翻倍
    对于使用电脑办公的上班族来说，提升工作效率和保证任务的准时完成是至关重要的。在电脑桌面上制作可视化进度日程待办清单，是实现这一目标的有效方法。因为这样能够让我们一目了然地了解当天及未来的工作任务，从而合理规划时间，确保每个任务都能得到妥善处理。那么我们如何在Windows......
  • 一道神奇的面试题---无序数组排序后的最大相邻差
    一：概述这个算法的面试题目是：有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。  二：具体说明<1>第一种解法(初步解法)这个解法的大致思路：使用任意一种时间复杂度为O(nlogn)的排序算法(如快速......
  • 生产设备机台文件导出，怎样兼顾文件的完整性和导出效率？
    生产设备是指用于制造、加工或生产产品或物品的机器、工具、设施、设备和仪器。它们在工业生产和制造业中扮演着关键的角色，帮助完成各种生产过程和操作。生产设备种类繁多，可以包括各种类型的设备，如机械设备、电子设备、自动化设备、仪器仪表、输送设备等。这些设备可以用于原材料......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99