几种简单的排序算法比较次数比较

1 说明

几种排序算法, 有一些是简单实现, 另有 glibc 的 qsort 和 GNU C++ 库的 std::sort. 下面的时间是排序 long 型数组的时间. 其实, 是一个 C 里 Sequence, 但此 Sequence 占用的时间和时间的误差相近, 在 10% 左右.

比较程序使用 random 生成数组, 在数组比较小时, 排序并打乱数组多次, 取时 间平均值, 最后几个, 因时间比较大, 只比较一次. 所以, 在所有的时间里, 有 打乱数组的时间开销, 大致为 O(size * time(random)). 本文只关心相对比较明 显的差异, 故不细分这些.

各排序算法如其名. 其中 quicksort_nr 是快速排序的非递归版, cqsort 是调 C 标准库函数 qsort. std::sort(iterator) 中的 get/set 不能区分, 统一计在 get 下.

C 的 qsort 由于必须有函数指针, 比较是相对较大开销, 所以在数组较小, 且内 存足够时采用需要额外内存但比较次数最少的归并排序. C++ 采用的是 quicksort 和 heapsort 的杂交 introsort, 比较次数相对归并排序多一点, 但 对整数而言, 比较仅是减法, 受限于内存访问的时间, 估可以次要考虑.

2 sort comparisons table

Algo.	Size	time	# comparisons/size	# gets/size	# sets/size
introsort	2^5	2.29932e-06	5.27492	9.38623	4.00063
heapsort	2^5	2.70095e-06	5.18218	13.2291	8.45347
mergesort	2^5	2.37965e-06	3.79695	9.29695	6
quicksort	2^5	2.19414e-06	5.56079	8.359	2.83799
quicksort_nr	2^5	2.15747e-06	5.36925	8.23558	2.85841
cqsort	2^5	2.98512e-06	3.79623	NA	NA
combsort	2^5	2.41381e-06	8.80184	17.6123	3.36478
std::sort(iterator)	32	4.68653e-06	5.95218	13.9444	NA
std::sort	32	1.65281e-06	5.94951	NA	NA
introsort	2^6	4.42774e-06	6.51571	11.0817	4.47673
heapsort	2^6	5.82915e-06	6.26207	15.305	9.46844
mergesort	2^6	4.97256e-06	4.76615	10.2662	6
quicksort	2^6	4.87501e-06	6.77834	10.0566	3.35011
quicksort_nr	2^6	4.76849e-06	6.60236	9.94205	3.3574
cqsort	2^6	6.40913e-06	4.76535	NA	NA
combsort	2^6	5.18118e-06	11.6094	23.2234	4.28761
std::sort(iterator)	64	3.99712e-06	7.11533	15.4967	NA
std::sort	64	3.62354e-06	7.12488	NA	NA
introsort	2^7	1.00313e-05	7.76488	12.8293	4.99319
heapsort	2^7	1.28292e-05	7.30858	17.3461	10.4755
mergesort	2^7	1.94854e-05	5.74942	13.2494	8
quicksort	2^7	1.06718e-05	7.98551	11.737	3.83951
quicksort_nr	2^7	1.05284e-05	7.80488	11.614	3.8471
cqsort	2^7	1.41386e-05	5.74657	NA	NA
combsort	2^7	1.22646e-05	14.5126	29.0274	5.30448
std::sort(iterator)	128	8.65036e-06	8.32369	17.1383	NA
std::sort	128	7.87806e-06	8.31551	NA	NA
introsort	2^8	2.16346e-05	8.96745	14.5286	5.49551
heapsort	2^8	2.79746e-05	8.33321	19.3682	11.4748
mergesort	2^8	2.38339e-05	6.74197	14.242	8
quicksort	2^8	2.26148e-05	9.21454	13.4375	4.31297
quicksort_nr	2^8	2.29063e-05	9.00217	13.2955	4.34143
cqsort	2^8	3.07402e-05	6.74541	NA	NA
combsort	2^8	2.71602e-05	17.383	34.7672	6.34737
std::sort(iterator)	256	1.99121e-05	9.54765	18.8368	NA
std::sort	256	1.73477e-05	9.57421	NA	NA
introsort	2^9	4.58946e-05	10.1556	16.2247	6.01352
heapsort	2^9	6.01988e-05	9.35496	21.3922	12.4821
mergesort	2^9	5.17732e-05	7.73911	17.2391	1NA
quicksort	2^9	4.92418e-05	10.3618	15.0615	4.8
quicksort_nr	2^9	4.81522e-05	10.1833	14.9512	4.81563
cqsort	2^9	6.54729e-05	7.74022	NA	NA
combsort	2^9	5.884e-05	20.3521	40.7047	7.38508
std::sort(iterator)	512	4.32935e-05	10.7954	20.6048	NA
std::sort	512	3.68822e-05	10.7974	NA	NA
introsort	2^10	0.000100438	11.3582	17.9356	6.51449
heapsort	2^10	0.000128305	10.361	23.3974	13.4805
mergesort	2^10	0.000106804	8.73833	18.2383	10
quicksort	2^10	0.000104649	11.5757	16.7461	5.26775
quicksort_nr	2^10	0.000102984	11.4302	16.6564	5.27142
cqsort	2^10	0.000185398	8.73907	NA	NA
combsort	2^10	0.000144469	23.9508	47.9019	8.49806
std::sort(iterator)	1024	8.9258e-05	11.9546	22.1866	NA
std::sort	1024	7.89147e-05	12.0618	NA	NA
introsort	2^11	0.000230655	12.5322	19.6955	7.09028
heapsort	2^11	0.000288267	11.3662	25.4025	14.4817
mergesort	2^11	0.000239689	9.7364	21.2364	12
quicksort	2^11	0.00024103	12.7323	18.3789	5.75391
quicksort_nr	2^11	0.000217546	12.5383	18.2607	5.76871
cqsort	2^11	0.000305481	9.737	NA	NA
combsort	2^11	0.000289749	27.0919	54.184	9.64027
std::sort(iterator)	2048	0.000190891	13.1735	23.8782	NA
std::sort	2048	0.00016664	13.1915	NA	NA
introsort	2^12	0.000462502	13.8416	21.6096	7.6772
heapsort	2^12	0.000570066	12.37	27.405	15.4825
mergesort	2^12	0.000510409	10.7365	22.2365	12
quicksort	2^12	0.000469625	13.9459	20.0833	6.24193
quicksort_nr	2^12	0.00046391	13.706	19.9027	6.24634
cqsort	2^12	0.000642657	10.7388	NA	NA
combsort	2^12	0.000638999	30.2622	60.5245	10.6047
std::sort(iterator)	4096	0.000405341	14.4655	25.6454	NA
std::sort	4096	0.000358723	14.6613	NA	NA
introsort	2^13	0.000944316	14.9803	23.2548	8.18111
heapsort	2^13	0.0012345	13.3728	29.4096	16.483
mergesort	2^13	0.00111294	11.7366	25.2366	14
quicksort	2^13	0.00100707	15.1234	21.7303	6.71223
quicksort_nr	2^13	0.000998065	14.8599	21.535	6.73174
cqsort	2^13	0.00133355	11.7354	NA	NA
combsort	2^13	0.00143582	33.8422	67.6845	11.7082
std::sort(iterator)	8192	0.000863686	15.7674	27.4121	NA
std::sort	8192	0.00074625	15.6189	NA	NA
introsort	2^14	0.00210512	16.126	24.9677	8.75029
heapsort	2^14	0.00262052	14.3694	31.4035	17.4816
mergesort	2^14	0.00231299	12.7382	26.2382	14
quicksort	2^14	0.00242236	16.1358	23.2343	7.2082
quicksort_nr	2^14	0.00239414	16.1299	23.2688	7.187
cqsort	2^14	0.00295651	12.7369	NA	NA
combsort	2^14	0.00316426	37.0912	74.1825	12.864
std::sort(iterator)	16384	0.00181475	17.1119	29.2536	NA
std::sort	16384	0.00160038	17.1486	NA	NA
introsort	2^15	0.00504923	17.3696	26.8373	9.35675
heapsort	2^15	0.00568175	15.3648	33.3989	18.474
mergesort	2^15	0.00549728	13.7331	29.2331	16
quicksort	2^15	0.00467777	17.7633	25.2896	7.6303
quicksort_nr	2^15	0.00500149	17.2662	24.8932	7.67592
cqsort	2^15	0.00653201	13.7351	NA	NA
combsort	2^15	0.0070073	40.2167	80.4334	13.9531
std::sort(iterator)	32768	0.00384778	18.3338	30.9398	NA
std::sort	32768	0.00335026	17.9507	NA	NA
introsort	2^16	0.00969255	18.5172	28.5819	9.94678
heapsort	2^16	0.0119691	16.3619	35.3975	19.4703
mergesort	2^16	0.0105975	14.7329	30.2329	16
quicksort	2^16	0.00940704	18.3235	26.4023	8.18502
quicksort_nr	2^16	0.00956297	18.1066	26.2475	8.1935
cqsort	2^16	0.0129935	14.7351	NA	NA
combsort	2^16	0.0143045	43.2142	86.4284	15.0652
std::sort(iterator)	65536	0.0081985	19.5519	32.6143	NA
std::sort	65536	0.0070591	19.4078	NA	NA
introsort	2^17	0.0198309	19.2521	29.6758	10.3184
heapsort	2^17	0.026468	17.3554	37.3895	20.462
mergesort	2^17	0.0243878	15.7346	33.2346	18
quicksort	2^17	0.024967	19.9184	28.4427	8.62446
quicksort_nr	2^17	0.0206831	19.6728	28.2809	8.6527
cqsort	2^17	0.028708	15.7364	NA	NA
combsort	2^17	0.031451	46.2132	92.4263	16.2224
std::sort(iterator)	131072	0.017206	20.7359	34.2805	NA
std::sort	131072	0.0147529	20.7001	NA	NA
introsort	2^18	0.0428371	20.7763	31.9917	11.08
heapsort	2^18	0.060225	18.354	39.3878	21.461
mergesort	2^18	0.054204	16.7354	34.2354	18
quicksort	2^18	0.0449061	20.9323	29.9506	9.11972
quicksort_nr	2^18	0.0444071	20.7911	29.8584	9.11888
cqsort	2^18	0.0612371	16.7355	NA	NA
combsort	2^18	0.0704291	49.2127	98.4253	17.2837
std::sort(iterator)	262144	0.0369871	21.8056	35.8416	NA
std::sort	262144	0.0335541	21.7911	NA	NA
introsort	2^19	0.10531	22.1166	33.9756	11.7039
heapsort	2^19	0.169231	19.354	41.3876	22.4603
mergesort	2^19	0.128936	17.7362	37.2362	20
quicksort	2^19	0.105645	22.1267	31.6042	9.58018
quicksort_nr	2^19	0.105005	22.234	31.7777	9.59514
cqsort	2^19	0.150182	17.7361	NA	NA
combsort	2^19	0.184128	52.2115	104.423	18.3483
std::sort(iterator)	524288	0.0942211	23.3306	37.815	NA
std::sort	524288	0.0859551	24.1802	NA	NA
introsort	2^20	0.247764	23.4475	36.0754	12.4453
heapsort	2^20	0.442663	20.3545	43.3887	23.4609
mergesort	2^20	0.290556	18.736	38.236	20
quicksort	2^20	0.250626	23.2412	33.2074	10.0712
quicksort_nr	2^20	0.253931	23.3071	33.3181	10.0623
cqsort	2^20	0.344221	18.736	NA	NA
combsort	2^20	0.43086	56.2095	112.419	19.3904
std::sort(iterator)	1048576	0.230459	23.9554	38.9847	NA
std::sort	1048576	0.20572	24.3193	NA	NA
introsort	2^21	0.554712	24.1748	37.1598	12.82
heapsort	2^21	1.07549	21.3544	45.3889	24.4613
mergesort	2^21	0.658452	19.7361	41.2361	22
quicksort	2^21	0.564909	24.3394	34.7983	10.5612
quicksort_nr	2^21	0.556773	24.0509	34.5808	10.582
cqsort	2^21	0.757419	19.7364	NA	NA
combsort	2^21	0.976948	59.2084	118.417	20.509
std::sort(iterator)	2097152	0.504422	25.5021	40.9916	NA
std::sort	2097152	0.472489	25.5631	NA	NA
introsort	2^22	1.20346	25.5088	39.1727	13.4783
heapsort	2^22	2.48213	22.3542	47.3885	25.4608
mergesort	2^22	1.38512	20.7357	42.2357	22
quicksort	2^22	1.2088	25.6059	36.5275	11.0243
quicksort_nr	2^22	1.19371	25.8683	36.813	10.995
cqsort	2^22	1.5637	20.7359	NA	NA
combsort	2^22	2.02832	62.2124	124.425	21.6898
std::sort(iterator)	4194304	1.07368	26.5342	42.514	NA
std::sort	4194304	0.977382	26.8222	NA	NA
introsort	2^23	2.48107	26.9948	41.4251	14.2166
heapsort	2^23	5.70184	23.3539	49.3881	26.4607
mergesort	2^23	2.93492	21.7357	45.2357	24
quicksort	2^23	2.53937	26.4896	37.9226	11.5348
quicksort_nr	2^23	2.52298	28.0309	39.3913	11.4106
cqsort	2^23	3.28481	21.7354	NA	NA
combsort	2^23	4.3994	66.2117	132.423	22.7599
std::sort(iterator)	8388608	2.23899	27.8882	44.3053	NA
std::sort	8388608	2.05833	27.8466	NA	NA
introsort	2^24	5.28411	28.7927	44.2796	15.2239
heapsort	2^24	12.9595	24.3541	51.3883	27.4607
mergesort	2^24	5.96994	22.7357	46.2357	24
quicksort	2^24	5.19425	27.9376	39.8182	11.9814
quicksort_nr	2^24	5.23735	27.9376	39.8573	11.9697
cqsort	2^24	6.77857	22.7356	NA	NA
combsort	2^24	8.84291	69.2087	138.417	23.8582
std::sort(iterator)	16777216	4.70659	28.795	45.7217	NA
std::sort	16777216	4.29975	29.2741	NA	NA