基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序

转载：在STL泛型算法中的排序函数sort内部使用的是哪种排序算法呢？
(2011-09-02 16:18:54)
标签：
杂谈
当你有一个数据序列时，你最想做的操作之一就是排序。将数据排序使得它易于被人理解，而且排序是许多泛型算法的第一步－－即使是计算一系列数字的和这样的微末算法。每个编程系统都提供了几种形式的排序；标准C++运行库提供了6种！(或可能更多，这取决于你怎么数了。)他们有多么大的差异，并且什么时候你该使用其中某一个而不是另外的那些？
用泛型算法进行排序
C++标准24章有一个小节叫“Sorting and related
operations”。它包含了很多对已序区间进行的操作，和三个排序用泛型算法：sort()，stable_sort()，和partial_sort()。
前两个，sort()和stable_sort()，本质上有相同的接口：同通常的STL泛型算法一样，传入指明了需要排序的区间的Random
Access Iterator。
同样，作为可选项，你也能提供第三个参数以指明如何比较元素：第三个参数是一个functor，接受两个参数(x和y)，在x应该位于y之前时返回true。所以，举例来说，如果v是一个int的vector：
std::sort(v.begin()， v.end());
将以升序来排序它。要改为降序，你需要提供应该不同的比较方法：
std::sort(v.begin()， v.end()， std::greaterint());
注意，我们正在以greater作为第三参数，而不是greater_equal。这很重要，它是所有STL排序算法的前提条件：比较函数必须在两个参数相同时返回false(WQ注：参看《Effective
STL》Item
21)。在某种程度上，这太武断了：看起来完全可以随便使用“”或者“=”这样形式的比较函数来表达一个排序算法的。然而，作出明确的选择是必需的，并且要始终坚持这个选择。标准C++运行库选择了前者。如果你传给sort()一个对等价的参数返回true的functor，你将得到不可预知的、完全依赖于具体实现的结果；在某些系统下，它看起来能工作，而在另外一些系统下可能导致无限循环或内存保护错误。
对于比较简单的场合，使用stable_sort()代替sort()，你不会看出很多差异。与sort()一样，stable_sort()对[first，
last)区间进行排序，默认是升序，并且，同样你可以提供一个比较函数以改变顺序。如果你读过C++标准，你将会看到sort()和stable_sort()的两个不同：
l
如名字所示，stable_sort()是稳定的。如果两个元素比较结果为等价，stable_sort()不改变它们的相对顺序。
l 性能上的承诺是不同的。
第一点，稳定，比较容易懂。它对int类型通常无所谓(一个“42”和另外一个“42”完全相同)，但有时对其它数据类型就非常重要了。比如，你正对task根据优先级排序，你或许期望高优先级的task被提到低优先级的task之前，但相同优先级的任务保持它们原来的先后顺序。sort()没有这个承诺，而stable_sort()承诺了这一点。
标准对性能的描述就不怎么直观了：sort()和stable_sort()的承诺都很复杂，并且都不完备。标准说sort()的“平均”复杂度是O(N
log N)，而没有说最坏的情况；stable_sort()的复杂度是O(N (log N)2)，但在有足够额外内存时同样是O( N
log N)。
怎样搞清楚所有这些不同情况？
性能的承诺是和特殊的实现技巧联系在一起的，而如果你知道这些技巧是什么的话，这个承诺就更明白了。允许sort()以快速排序(递归分割区间)来实现，而stable_sort()以归并排序(递归归并已序子区间)来实现[注1]。快速排序是已知的最快速排序算法之一，复杂度几乎总是O(N
log N)，但对一些特殊序列是O(N2)；如果标准总要求sort()是O(N log
N)，将不能使用快速排序。同样，归并两个子区间在有额外缓冲区以拷贝结果时将很容易实现；归并排序在可以使用与原始区间同样大的辅助缓冲区时是O(N
log N)，如果不能获得任何辅助缓冲区时是O(N (log
N)2)。如果它只能使用一个较小的辅助缓冲区，复杂度将在两者之间－－但，在现实中，更接近于O(N log N)。
这解释了标准中说的东西，但还不全。标准说“如果最坏情况时的行为很重要”，你就不该使用sort()。然而，事实并不象标准第一次写下这条建议时那样。许多标准运行库的实作，包括GNU
g++和Microsoft Visual
C++，现在使用快速排序的一个新的变种，称为introsort[注2](WQ注：参看侯捷《STL源码剖析》)。Introsort一般说来和快速排序同样快，但它的复杂度总是O(N
log N)。 除非你顾虑老的标准库的实作，最差情况时的行为不再成为避免使用sort()的理由。并且，虽然stable_sort
(通常)也是O(N log N)，这个O掩盖了很多细节。
在绝大多数情况下，stable_sort()比sort()慢很多，因为它必须对每个元素作更多操作；这就是你要为“稳定”付出的代价。使用stable_sort()应付等价元素维持原来的相对顺序很重要的情况(比如，根据优先级进行排序，但要对相同优先级的条目保持先来先处理的顺序)，而使用sort()处理其它情况。
另一个泛型排序算法是partial_sort()(包括一个小变种，partial_sort_copy())。它的功能稍有不同，语法也稍有区别：它查找并排序区间内的前n名元素。和其它情况一样，默认是通过“”比较进行升序排列，但能提供一个functor来改变它。于是，举例来说，如果你只对序列的前10名的元素感兴趣，可以这样找到它们：
partial_sort(first， first+10， last， greaterT());
然后，最大的10个元素将被容纳在[first， fist + 10)(降序排列)， 其余元素容纳在[first + 10，
last)。
这儿有一个明显的受限情况：如果你写partial_sort(first， last，
last)，那么你正要求partial_sort()排序整个[first，
last)区间。于是，虽然语法稍有不同，你能仍然能以使用sort()的同样的方法使用partial_sort()。有理由这么做吗？实际是没有。查看一下C++标准对复杂度的描述，你将看到partial_sort()和sort一样，也是O(N
log N)，但是，再一次，这是不完全的描述。两个O(N log
N)的运算不必然有同样的速度；对此例，sort()通常快得多。
partial_sort()的存在是为了部分排序。假如你有一个一百万个名字的列表，而你需要找前一千个，按字母排序。通过对整个列表排序并忽略后面的部分，你可以得到这一千个名字，但那会非常浪费。使用partial_sort()或partial_sort_copy()会快得多：
vectorstring result(1000);
partial_sort_copy(names.begin()， names.end()， result.begin()，
result.end());
当你只对已序区间的前面部分感兴趣时，使用partial_sort()，而在需要排序整个区间时使用sort()。
如对sort()和stable_sort()所做过的，考查一下partial_sort()是如何实现的将会有帮助。通常的实现，也是C++标准制订者建议的，是使用堆排序：输入区间在一个称为heap的数据结构中重新整理，heap本质上是一个用数组实现的二叉树，它很容易找到最大的元素，并且很容易在移除最大元素时仍然保持为一个有效heap。如果我们连续地将元素从一个heap中移开，那么将会留下最小的n个元素：正是我们想从partial_sort获得的。如果从heap中移除所有元素，将会得到一个已序区间。
标准C++运行库包含了直接操纵heap的泛型算法，所以，代替使用 partial_sort()，要排序一个区间可以写：
make_heap(first， last);
sort_heap(first， last);
这看起来和
partial_sort(first， last， last);
不同，但其实不是这样。两种情况下，你都使用了堆排序；两种形式应该具有完全相同的速度。
最后，还有最后一个“泛型”排序算法，从C语言继承而来：qsort()。
对“泛型”加引号，是因为qsort()实际上不象sort()、stable_sort()和partial_sort()那样通用。不能用它排序具有构造函数、虚函数、基类或私有数据成员的对象。C语言不知道这些特性；qsort()假设它可以按位拷贝对象，而这只对最简单的class才成立。也很难在模板中使用qsort()，因为你必须传给它一个参数是void
*类型的比较函数，并且在这个函数内部知道要排序的对象的精确类型。
C语言标准没有对qsort()作出性能承诺。在可以使用qsort()的场合，通常表现得比sort()慢很多。(主要是因为一个简单的原因：sort()的接口被设计得可以将比较函数内联，而qsort()的接口做不到这一点。)除非是遗留代码，你应该避免使用qsort()；sort()具有一个更简单并且更安全的接口，它的限制比较少，而且更快。
对特别的容器进行排序
我以讨论泛型算法开始，是因为标准C++运行库的基本原则是解耦不必要耦合的事物。算法被从容器中分离出来。在对容器的需求中，没有提到排序；排序一个vector是使用一个独立于std::vector的泛型算法：
sort(v.begin()， v.end());
然而，任何对C++中的排序的完备讨论都必须包括容器。通常，容器没有提供排序方法，但一些特殊的容器提供了。
你不能通过写v.sort()来排序一个vector，因为std::vector没有这样的成员函数，但你可以通过写l.sort()来排序一个list。和往常一样，你可以显式地提供一个不同的比较函数：如果l是一个int型的list，那么l.sort(greaterint())将按降序排序它。
事实上，list::sort()是排序一个list的唯一的容易方法：std::list只提供了Bidirectional
Iterator，但独立的泛型排序算法(sort()、stable_sort()和partial_sort())要求更强大的Random
Access
Iterators[注3]。这个特别的成员函数list::sort()不使用iterator，于是暴露了list是以相互连接的节点来实现的事实。它使用归并排序的一个变种，通过连接和解连节点来工作，而不是拷贝list中的元素。
最后，排序一个set(或一个multiset，如果你需要拥有重复元素)是最简单的：它本来就是已排序的！你不能写sort(s.begin()，s.end())，但你也从不需要这么做。set的一个基本特性是它的元素按顺序排列的。当你insert()一个新元素时，它自动将它放置在适当的位置以维持排序状态。在其内部，set使用一个能提供快速(O(log
N))的查找和插入的数据结构(通常是某种平衡树)。
时间测试
这将我们置身何处？我已经对时间作了一些论断，而且我们还能作些更直觉的预测：比如，在set中插入一个元素将比排序一个vector慢，因为set是一个复杂的数据结构，它需要使用动态内存分配；或者，排序一个list应该和使用stable_sort差不多快，它们都是归并排序的变种。然而，直觉不能取代时间测试。测量很困难
(更精确地说，你要测量什么，又如何测量？)，但这是有必要的。
Listing
1的程序构造了一个vectordouble，其中的元素乱序排列，然后用我们讨论过的每个方法(除了qsort()(WQ注：原文如此))反复对它进行排序。在将vector传给每个测试用例时，我们故意使用传值：我们不想让任何一个测试用例得到一个已排序的vector！
用Microsoft Visual C++ 7 beta编译程序(结果和g++相似)，在500M的Pentium
3上进行，结果如下：
Sorting a vector of 700000 doubles.
sorting method t (sec)
sort 0.971
qsort 1.732
stable_sort 1.402
heap sort 1.282
list sort 1.993
set sort 3.194
这和期望相符：sort()最快；stable_sort()、堆排序和qsort()稍慢；排序一个list和set(它使用动态内存分配，并且是个复杂的数据结构)，更加慢。
(实际上，qsort()有一个不寻常的好成绩：在g++和VC的老版本上，qsort()仅比sort()慢。)
但这不足以称为排序基准测试－－太不具有说服力了。我在一个特定的系统上，使用一个特定的(乱序)初始化，来测试排序一个vectordouble。只有实践能决定这些结果有多大的普遍性。至少，我们应该在double以外再作些测试。
Listing
2排序一个vectorstring：它打开一个文件并将每一行拷贝进一个独立的string。因为qsort()不能处理具有构造函数的元素，所以这个测试中不再包括qsort()。以Project
Gutenberg的免费电子文本《Anna Karenina》[注4]作为输入，结果是：
Sorting a file of 42731 lines.
sorting method t (sec)
sort 0.431
stable_sort 1.322
heap sort 0.751
list sort 0.25
set sort 0.43
突然之间，事情发生了变化。我们仍然看到sort()比stable_sort()和堆排序快得多，但list和set的结果发生了戏剧性的变化。使用set的速度几乎和sort()一样，而list实际上更快。发生了什么？
变化是double是原生类型，而std::sting是一个复杂的class。拷贝一个string或将它赋值给另一个，意味着要调用一个函数－－甚至意味着需要使用动态内存分配或创建一个mutex锁。平衡点被改变了；排序string比排序double时，赋值的次数将有更多的影响。排序一个list时，根本没有调用赋值运算：定义一个特别的list::sort()成员函数的全部理由就是它通过操纵指向list的内部节点的指针来工作的。重连接一些list的node的指针比拷贝一个string快。
我们再度发现一个老的至理名言：如果你正在处理大的记录，你绝不要排序记录本身，排序指向它们的指针。使用list使得这一点成为自动，但你也能很容易地显式做到这一点：不是排序原始的vectorstring，取而代之，创建一个索引vector，其元素类型是vectorstring::const_iterator，然后排序这个索引vector。你必须告诉sort()如何比较索引vector的元素(你必须确保比较的是iterator所指的值而不是iterator本身)，不过这只是个小问题。我们只需提供一个合适的比较函数对象：
template class Iterator
struct indirect_lt {
bool operator()(Iterator x， Iterator y) const
{ return *x*y; }
};
Listing 3展示了如何使用indirect_lt，并对比了直接排序和间接排序时的速度。速度的提升是显著的。
Sorting a file of 42731 lines.
sorting method t (sec)
indirect sort 0.29
sort 0.401
建议
标准C++运行库提供了六个排序方法：qsort()，sort()，stable_sort()，partial_sort()，lsit::sort()，和set/multiset。
你不应该在新代码中使用qsort()。它比sort()慢。它的接口丑陋，因为它需要类型转换，并易于用错。写一个比较函数以传给qsort()可能很麻烦，尤其是在泛型代码中。你不能使用qsort()排序有构造函数或虚函数的东西，或排序C语言的数组以外的任何数据结构。虽然qsort()没有正式说不推荐使用，但它唯一真正的用处是对C语言的向后兼容。
在其它五个排序方法中，前三个是泛型算法，后两个则使用了某些容器的特别特性。所有这些方法默认都使用operator()来比较对象，但允许在必要时指定用户自己的比较函数。每个都提供了一些特别的特征：
l sort()通常最快。
l stable_sort()保证了等价元素在顺序上的稳定。
l partial_sort()允许只排序出前N个元素。
l list::sort()操纵指针，而不是拷贝元素。
l set允许在一个已序区间快速的插入和删除
分享：
喜欢
0
赠金笔
加载中，请稍候......
评论加载中，请稍候...
发评论
登录名：   密码：   找回密码   注册记住登录状态
昵   称：
发评论
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

排序方法/特点
			
稳定性
			
时间复杂度
			
 
		
冒泡排序
			
稳定
			
O(n^2)
			
 
		
直接插入排序
			
稳定
			
O(n^2)
			
 
		
希尔排序
			
不稳定
			
O（n^1.3）
			
 
		
选择排序
			
不稳定
			
O(n^2)
			
 
		
快速排序
			
不稳定
			
 O(nlog2 n)
			
 
		
堆排序
			
不稳定
			
O(nlogn)
			
 
		
归并排序
			
稳定
			
O(nlog2 n)
			
 
		
基数排序
			
稳定
			
O(kn)
			
 
		
从平均情况看：堆排序、归并排序、快速排序胜过希尔排序。

从最好情况看：冒泡排序和直接插入排序更胜一筹。

从最差情况看：堆排序和归并排序强过快速排序。

虽然直接插入排序和冒泡排序速度比较慢，但是当初始序列整体或局部有序是，这两种算法的效率比较高。当初始序列整体或局部有序时，快速排序算法效率会下降。当排序序列较小且不要求稳定性是，直接排序效率较好；要求稳定性时，冒泡排序法效率较好

下图是常见排序算法的最好，最坏，平均时间复杂度、空间复杂度，稳定性总结表。



 直接看表格，综合时间复杂度、空间复杂度等各种因素，目测堆排序是最优选择。不管最好、最坏还是平均情况，时间复杂度都是O(nlogn)，而且还不像快排排序和归并排序那样占空间，计数排序、基数排序、桶排序空间复杂度太大，需要消耗大量额外空间。

快速排序和堆排序

接下来亲自比较一下，快速排序和堆排序到底谁效率更高。附上快速排序和堆排序的代码（其中，快速排序使用《编程珠玑》第二版第11章中的方法，堆排序使用第14章中的方法）。

//快速排序
void swap(int*a, int*b){
	int temp = *a;
	*a = *b;
	*b = temp;
}
void quicksort(int *a, int l, int u){
	if (l >= u) return;
	srand(time(NULL));
	int j = (rand() % (u - l + 1)) + l;
	swap(&a[l], &a[j]);
	int m = a[l];
	int index = u + 1;
	for (int i = u; i >= l; i--)
	{
		if (a[i] >= m)
			swap(&a[i], &a[--index]);
	}
	quicksort(a, l, index - 1);
	quicksort(a, index + 1, u);
}


//堆排序
vector<int> x;
void swap(int *a, int *b){
	int temp = *a;
	*a = *b;
	*b = temp;
}
void siftup(int n){
	int i, p;
	for (i = n; i > 1 && x[p = i / 2] > x[i]; i = p) {
        swap(&x[i],&x[p]);
	}
}
void siftdown(int n)
{
	int i, c;
	for (i = 1; (c = 2 * i) <= n; i = c)
	{
		if (c + 1 <= n && x[c + 1] < x[c])c++;
		if (x[i] <= x[c])break;
        swap(&x[i],&x[c]);
	}
}

下面是本人在自己电脑上测试的结果，win7系统，i7 7代CPU，8G内存。 



不比不知道，一比吓一跳，数据规模越大，快速排序的优势越来越大，Why？？？ 难道只从复杂度角度判断算法优劣有问题？？？

从复杂度角度判断算法其实也没什么问题，只能说是想的太少了，结合到实际的内存存储问题，数据频繁交换、写入、移除、调整等问题，堆排序要大很多。

在堆排序（小根堆）的时候，每次总是将最小的元素移除，然后将最后的元素放到堆顶，再让其自我调整。这样一来，有很多比较将是被浪费的，因为被拿到堆顶的那个元素几乎肯定是很大的，而靠近堆顶的元素又几乎肯定是很小的，最后一个元素能留在堆顶的可能性微乎其微，最后一个元素很有可能最终再被移动到底部。在堆排序里面有大量这种近乎无效的比较。随着数据规模的增长，比较的开销最差情况应该在（线性*对数）级别，如果数据量是原来的10倍，那么用于比较的时间开销可能是原来的10log10倍。

        堆排序的过程中，需要有效的随机存取。比较父节点和字节点的值大小的时候，虽然计算下标会很快完成，但是在大规模的数据中对数组指针寻址也需要一定的时间。而快速排序只需要将数组指针移动到相邻的区域即可。在堆排序中，会大量的随机存取数据；而在快速排序中，只会大量的顺序存取数据。随着数据规模的扩大，这方面的差距会明显增大。在这方面的时间开销来说，快速排序只会线性增长，而堆排序增加幅度很大，会远远大于线性。

        在快速排序中，每次数据移动都意味着该数据距离它正确的位置越来越近，而在堆排序中，类似将堆尾部的数据移到堆顶这样的操作只会使相应的数据远离它正确的位置，后续必然有一些操作再将其移动，即“做了好多无用功”。

在《编程珠玑》一书中，编者建议我们使用C/C++标准函数库中的sort函数。

C++标准库里的sort()函数

为什么要用c++标准库里的排序函数?

Sort函数包含在头文件为#include<algorithm>的c++标准库中，调用标准库里的排序方法可以不必知道其内部是如何实现的，只要出现我们想要的结果即可！

Sort()函数是c++一种排序方法之一，学会了这种方法也打消我学习c++以来使用的冒泡排序和选择排序所带来的执行效率不高的问题！貌似它是使用者的输入数据来选择最优的排序算法，执行效率较高！

sort函数有三个参数：

（1）第一个是要排序的数组的起始地址。

（2）第二个是结束的地址（最后一位要排序的地址）

（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。



（参考《编程珠玑》第二版第11章）

进击的排序

我在某论坛里看到有人提到使用位图排序，稍微看了一下，没有仔细研究！

贴上网上抄袭的电话号码排序问题实现算法。

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <bitset>
using namespace std;

void randInt(int n, int m, int arrayM[])
{
	srand(time(0)); 
	int *arrayN = new int[n];
	for (int i = 0; i < n; i++) 
		arrayN[i] = i + 1;

	for (int i = 0; i < n; i++) {
		int temp, rint;
		rint = rand() % n;
		temp = arrayN[i];
		arrayN[i] = arrayN[rint];
		arrayN[rint] = temp;
	}

	for (int i = 0; i < m; i++) 
		arrayM[i] = arrayN[i];
}

int main(){
	int n = 10, m = 5;
	int *arrayM = new int[m];
	randInt(n, m, arrayM);
	cout << "orginal number: ";
	for (int i = 0; i < m; i++) 
		cout << arrayM[i] << " ";
	cout << endl;
	bitset<10> abit;
	abit.reset();
	for (int i = 0; i < m; i++) 
		abit.set(arrayM[i] - 1);  
	cout << "sorted number: ";
	for (int i = 0; i < n; i++) 
		if (abit.test(i))
			cout << i + 1 << " ";
	cout << endl;
	return 0;
}

参考文献：《编程珠玑》第二版

https://blog.csdn.net/u010189459/article/details/27702027