该比武只比速度,单线程测试随机正整数,不包括蜗牛排序,它弃权啦,哈哈。

操作系统:Windows XP Pro SP3,英文版
编译器:g++4.5.2(-O3)
CPU: Intel Core2 Q9500
内存:DDR3普条 1066MHz, 4GB

插入排序、选择排序和冒泡排序最慢,时间复杂度为O(n2),希尔排序的速度依赖于使用的增量序列,堆排序、归并排序和改进的快速排序处于中等水平,时间复杂度为O(nlogn),计数排序、基数排序以及桶排序最快,时间复杂度为O(n) 

前面已经说过,标准库中收录了堆排序、改进的快速排序和归并排序,它们的理论速度处于中上等水平,却没有收录理论速度更快的计数排序、基数排序和桶排序中的任何一种,这究竟因为何故?相信太多人弄不明白其中的道理。原因其实很简单,因为时间复杂度为O(n)的这三种排序实际表现不佳,空间开销太大,且具体实现严重依赖数据类型。

为了检验上述排序算法的性能,用随机数序列做了正序排序测试,除了计数排序外,其它排序测试数值范围为[0, 2147483648),各种排序耗费的时间见下表。

简单比较排序,时间复杂度一般为O(n2),希尔排序的时间复杂度依赖于使用的序列,使用Hibbard序列时,希尔排序时间复杂度最差为O(n3/2),使用Sedgewick序列时,希尔排序时间复杂度最差为O(n4/3),简单排序的空间复杂度均为O(1)

把一个随机序列排序成升序序列(单位:毫秒)

数据量

插入排序

选择排序

冒泡排序

希尔排序

直接插入

二分插入

Hibbard

Sedgewick

1.0e+1

0.000525

0.000638

0.000700

0.000651

0.000570

0.000689

1.0e+2

0.004058

0.006403

0.010846

0.017810

0.004805

0.005292

1.0e+3

0.248739

0.241721

0.709755

1.76696

0.075513

0.075307

1.0e+4

23.6821

18.5430

65.0864

175.155

1.13762

1.11278

1.0e+5

2334.46

1799.45

6445.43

17642.6

15.4906

15.7181

1.0e+6

241898

188869

660667

1819720

218.087

206.449

1.0e+7

---

---

---

---

2892.09

2731.79

1.0e+8

---

---

---

---

39645.8

30624.1

把一个升序序列排序成升序序序列(单位:毫秒)

数据量

插入排序

选择排序

冒泡排序

希尔排序

直接插入

二分插入

Hibbard

Sedgewick

1.0e+1

0.000431

0.000497

0.000576

0.000413

0.000471

0.000604

1.0e+2

0.000705

0.001689

0.007730

0.000515

0.001762

0.002578

1.0e+3

0.005211

0.023300

0.654459

0.001495

0.024479

0.026534

1.0e+4

0.032183

0.261476

64.6679

0.011198

0.387672

0.383410

1.0e+5

0.326892

3.31448

6462.27

0.106789

5.00605

5.11000

1.0e+6

3.25322

40.2028

661825

1.14374

66.9433

66.3024

1.0e+7

31.2321

477.013

---

11.9349

828.123

803.050

1.0e+8

306.505

5550.34

---

118.441

9476.97

9471.65

把一个降序序列排序成升序序列(单位:毫秒)

数据量

插入排序

选择排序

冒泡排序

希尔排序

直接插入

二分插入

Hibbard

Sedgewick

1.0e+1

0.000528

0.000580

0.000633

0.000512

0.000462

0.000618

1.0e+2

0.004795

0.005481

0.008988

0.006476

0.0025228

0.003193

1.0e+3

0.362995

0.376571

0.690305

0.539237

0.0324535

0.033210

1.0e+4

35.5184

35.6372

67.7467

65.3332

0.510507

0.447574

1.0e+5

3546.92

3546.18

6776.27

8990.63

6.42464

5.74839

1.0e+6

432377

431580

694979

617435

83.7521

79.7468

1.0e+7

---

---

---

---

988.176

949.626

1.0e+8

---

---

---

---

11734.7

11063.1

从上面三个表可以看出,当数据量很小时,直接插入排序由于开销很小,因此速度很快。当一个序列已经有序时,冒泡排序速度最快,其它情况,冒泡排序的速度最慢(本文没有针对这种情况给出更详细的测试结果)。尽管希尔排序仅仅是插入排序的一个变种,但是在一般场合,希尔排序的速度会遥遥领先于插入排序,甚至可以与时间复杂度为O(nlogn)的堆排序匹敌。

复杂的比较排序,时间复杂度一般为O(nlogn),原地归并排序时间复杂度为O(nlog2n)。堆排序的空间复杂度为O(1),快速排序和原地归并排序的空间复杂度一般为O(logn),带缓冲区的归并排序的空间复杂度一般为O(n)

把一个随机序列排序成升序序列(单位:毫秒)

数据量

堆排序

快速排序

归并排序

sort

sort_r

quick_sort

qsort

原地归并

有缓冲区

1.0e+1

0.000642

0.000540

0.000541

0.000706

0.000868

0.000535

0.000716

1.0e+2

0.005120

0.003417

0.003409

0.005350

0.008928

0.013398

0.003947

1.0e+3

0.064826

0.041792

0.042142

0.062889

0.117883

0.256407

0.048691

1.0e+4

0.826593

0.536043

0.539067

0.755660

1.50353

4.17856

0.633436

1.0e+5

10.7042

6.59608

6.62956

8.84884

18.3578

55.4733

7.91912

1.0e+6

158.744

78.4110

79.1261

101.926

214.367

697.286

99.3735

1.0e+7

3773.92

912.128

927.636

1152.59

2530.75

8810.93

1137.64

1.0e+8

60973.9

10352.9

10516.4

12822.2

28351.3

105516

13091.4

把一个升序序列排序成升序序列(单位:毫秒)

数据量

堆排序

快速排序

归并排序

sort

sort_r

quick_sort

qsort

原地归并

有缓冲区

1.0e+1

0.000513

0.000435

0.000439

0.000506

0.000595

0.000433

0.000602

1.0e+2

0.003738

0.001177

0.001394

0.002452

0.003632

0.002530

0.001744

1.0e+3

0.055996

0.008555

0.012148

0.019437

0.044580

0.024222

0.014240

1.0e+4

0.545597

0.115373

0.138347

0.200567

0.521049

0.335698

0.162571

1.0e+5

5.95518

1.18510

1.60851

2.14343

6.21663

2.71505

2.00932

1.0e+6

70.4104

11.8008

18.5488

25.5529

75.1664

24.1894

38.5684

1.0e+7

803.386

157.113

211.240

281.599

880.122

349.296

439.614

1.0e+8

9262.68

1653.56

2526.51

2994.46

9633.74

2792.79

5093.96

把一个降序序列排序成升序序列(单位:毫秒)

数据量

堆排序

快速排序

归并排序

sort

sort_r

quick_sort

qsort

原地归并

有缓冲区

1.0e+1

0.000533

0.000488

0.000501

0.000508

0.000674

0.000498

0.000611

1.0e+2

0.003663

0.001053

0.001488

0.002456

0.004197

0.004880

0.001840

1.0e+3

0.054465

0.007733

0.013793

0.019849

0.049924

0.055198

0.015355

1.0e+4

0.590327

0.106844

0.152277

0.203784

0.578746

0.729590

0.172541

1.0e+5

6.52191

1.10164

1.72681

2.16512

6.79996

7.61116

2.14922

1.0e+6

79.4964

12.3473

19.2062

25.5790

79.5690

82.7066

40.8505

1.0e+7

928.131

164.947

218.357

288.926

922.900

1127.96

460.994

1.0e+8

10697.4

1737.03

2468.51

3067.36

10074.7

13125.3

5327.67

可以看出,在时间复杂度为O(nlogn)的排序算法里,堆排序最慢,优化的快速排序sort排序速度最快,随机选取支点的快速排序sort_r仅次于sort,当对一个随机序列排序时,二者速度差距很小,原始的快速排序quick_sort(用了两个递归)速度比较慢,可以看出,递归程序的执行效率还是很低的,C库函数qsort在几个版本的快速排序里面垫底,主要原因是比较函数无法被编译器内联。原地归并排序虽然稳定且节约内存,但速度最慢,带缓冲区的归并排序速度还是蛮不错的。

理论时间复杂度为O(n)的计数排序、基数排序和桶排序的空间复杂度均为O(n),且只能针对特殊数据类型排序,排序速度跟具体实现也有很大关系。

把一个随机序列排序成升序序列(单位:毫秒)

数据量

计数排序

基数排序

桶排序

1.0e+1

400.842

0.074379

0.001169

1.0e+2

488.821

0.077817

0.005455

1.0e+3

500.421

0.106693

0.053476

1.0e+4

500.097

0.376948

0.423485

1.0e+5

515.160

3.30198

5.24631

1.0e+6

666.797

63.2423

74.9957

1.0e+7

2254.77

1208.84

1024.32

1.0e+8

21174.0

14565.8

20708.8

把一个升序序列排序成升序序列(单位:毫秒)

数据量

计数排序

基数排序

桶排序

1.0e+1

386.154

0.075321

0.001019

1.0e+2

487.709

0.079056

0.002017

1.0e+3

496.003

0.108765

0.013471

1.0e+4

499.207

0.379271

0.125317

1.0e+5

506.460

3.35299

1.64946

1.0e+6

550.123

62.4690

25.2364

1.0e+7

778.383

1199.67

269.743

1.0e+8

1878.57

15381.4

2771.17

把一个降序序列排序成升序序列(单位:毫秒)

数据量

计数排序

基数排序

桶排序

1.0e+1

398.474

0.075307

0.001106

1.0e+2

489.401

0.079179

0.006004

1.0e+3

495.684

0.103746

0.062618

1.0e+4

500.081

0.339944

0.451859

1.0e+5

505.583

3.23047

5.83522

1.0e+6

525.979

61.7166

75.5025

1.0e+7

774.020

1209.40

595.325

1.0e+8

1697.88

15648.1

6643.6

对比计数排序、基数排序和桶排序的测试结果容易看出,这三款时间复杂度为O(n)的排序算法速度相差不大,对一个随机整数序列的排序时,基数排序略占上风。

时间复杂度为O(n)的计数排序、基数排序和桶排序均跟不上时间复杂度为O(nlogn))的快速排序sort的脚步,原因详见本主页基数排序。