該比武只比速度，單線程測試隨機正整數，不包括蝸牛排序，它棄權啦，哈哈。

操作系統：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的腳步，原因詳見本主頁基數排序。