本文共 2567 字，大约阅读时间需要 8 分钟。

Conclusions

I can’t claim that C++ is always faster than C. However, I do claim that C++ templates offer a way to provide library routines that offer the traditional advantages of library routines (ease of use, flexibility) yet still are able to provide speed close to hand-written code. This combination is generally unavailable to programmers using C (or Pascal, or Basic, or Java, or …). When I programmed in C, I always had to choose between library routines and hand-written code. In C++, I choose (STL) library routines whenever possible. I usually get better (faster and more flexible) code than I would have written myself (without putting in a lot of effort). It’s refreshing to finally be able to use library routines without expecting any performance penalties.

Comparison of algorithms

Name	Average	Worst	Memory	Stable	Method	Other notes
	02 	03 	01 	Yes	Exchanging
	03 —	03 	01 	Yes	Exchanging
	03 —	04 —	01 	No	Exchanging	Small code size
	03 —	03 	01 	Yes	Exchanging	Tiny code size
	02 	03 	01 	No	Selection
	02 	03 	01 	Yes	Insertion	Average case is also , where d is the number of
	03 —	02 	01 	No	Insertion
	01 	01 	03 	Yes	Insertion	When using a
	01 	03 	03 	Yes	Insertion
	01 	01 	03 	Yes	Merging
	01 	01 	01 	No	Merging	Example implementation here: ; can be implemented as a stable sort based on stable in-place merging:
	01 	01 	01 	No	Selection
	03 —	01 	01 	No	Selection	An - comparisons when the data is already sorted, and swaps.
	01 	03 	02 	No	Partitioning	variants use space
	01 	01 	02 	No	Hybrid	Used in implementations
	03 —	01 	03 	No	Insertion & Selection	Finds all the within O(n log n)
	01 	03 	03 	Yes	Selection
	01 	01 			Selection

插入排序： 稳定， O(n²)。

冒泡排序： 稳定， O(n²)。

选择排序： 不稳定， O(n²)。

堆排序： 不稳定， O(n log n)。

快速排序： 不稳定， O(n log n)。

希尔排序：O(n^1.25)。

基数排序：O(n)。

桶排序：。

选择排序的平均时间复杂度比冒泡排序的稍低: 

希尔排序实质上是一种分组插入方法。

转载地址：http://ohntb.baihongyu.com/