算法无极限
排序算法（上）
排序(sort)一直是算法世界最重要的算法，由于排序算法简练而又复杂多变，实现方法灵活，人们称它们为捕鼠器。至今，已有10类左右的排序算法，但依然有人在为发明新捕鼠器而默默努力。在这些算法中，每一类都建立在自己独特的方法论上，有着性能和适应性上的差异。有些适合规模小的数据，有些适用于大型规模的数据。有些应用在随即分布的数据上能获得高效率，而另一些适用于特殊的数据分布（接近有序，反序，多重复值等）。在这里，我想对各种的排序方法进行介绍和分析其性能特点。
在讨论具体算法之前，我们先来规定一下约定用语。
a.下面的都是基于数组的，给出代码为标准c++。（基于链表的排序在最后介绍）
b.排序算法的函数参数是(a[],l,t),a[]是输入数据的数组，l是第一个要处理的数据的N指数据的数量。
c.所有算法都是将a[]里的元素进行升序排序，元素的最终位置指排序完成后所处的位置。
d.算法中使用的两个基本函数exch(交换)和compexch(比较交换)定义为:
template<class Item> void exch(Item& A,Item& B){ Item t=A;A=B;B=t;}
template<class Item> void compexch(Item& A,Item& B){ if(B<A) exch(A,B);}
选择，插入，冒泡
选择排序，插入排序和冒泡排序是3种基本的排序方法。其特点是直接，易于实现。虽然在实际使用不多，但常常作为其他算法的组成部分。同时它们是学习排序算法的基础，必须认真的学习。
选择排序(selection sort)
选择排序方法是，遍历数据，每次找出最小的元素，把它放到相应的位置上。它的特点是“绝不向后看”，每一轮循环都将最小元素放到最终的位置。因此，在最坏情况下，它需要进行N2/2 次比较和N 次交换。
//选择排序
template<class Item>
void selection(Item a[], int l,int r){
for(int i=l;i<r;i++){
int min=i;
for(int j=i+1;j<=r;j++)
if(a[j]<a[min])
min=j;
exch(a[i],a[min]);
}
}
选择排序是所有排序算法中需要的交换次数是最少的，其交换数等于不在最终位置上的元素个数。因此它适合用于|values|较大而|keys|较小的数据或交换所需代价的大数据。（对于键-值对的数据，将它所有值的集合成为values，所有键的集合成为keys。 |values|,|keys|分别值不同的值的个数和不同键的个数。）
插入排序(insertion sort)
插入排序使用的方法是，将下一个元素插入到已经排序好大小为n的序列中，将它放到相应的位置之成为大小为n+1序列，然后继续处理下一个元素。它的特点是“绝不往前看”，也就是在处理第n个数据时，不考虑第n个以后的数据。
//插入排序
template<class Item>
void insertion(Item a[],int l,int r){
int i;
for(i=r;i>l;i--) compexch(a[i-1],a[i]); //将最小的元素移到首位
for(i=l+2;i<=r;i++){
int j=i;
Item v=a[i];
while(v<a[j-1]){
a[j]=a[j-1];
j--;
}
a[j]=v;
}
}
插入排序在平均情况下需要进行N2/4次比较和半交换(移动)。而在最坏情况下，如a[]是反序时，它需要进行的操作将加倍。另一方面，当a[]是已经排列好或接近排练好时，它只需少量的操作。因此插入排序非常适用于接近有序的数据。
冒泡排序
冒泡排序是通过N次遍历，反复比较交换(compexch)相邻两个元素，将最小元素沉淀到数组前端的算法。它的实现十分简洁，只需两个嵌套的for语句。同时由于它适用蛮干策略，它的平均情况，最怀情况和最优情况都需要进行N2/2次比较交换。
//冒泡排序
template<class Item>
void bubble(Item a[],int l,int r){
for(int i=l;i<r;i++)
for(int j=r;j>i;j--)
compexch(a[j-1],a[j]);
}
基本排序法的扩展
选择，插入和冒泡3中基本排序法都不太适用于大规模的数据。因此，人们发明了它们的一些扩展方法，用于提高其效率。
shell排序(shellsort)
shell排序是对插入排序的扩展，插入排序是对相邻的元素进行插入处理，而shell排序是对间隔的元素进行插入处理。它从一个递增整数序列中取出最大1项，用它作为间隔，将所间隔的元素看成要进行插入排序的序列。例如(当h=4时，取出第1，5，9...个元素进行插入排序，然后再取出2，6,10...个元素进行插入排序，如此类推) 完成后在从整数数列中选择前一个数，进行同样操作。直到最后，选择整数1，进行常规的插入排序。
shell排序这样做的目的是避免一般插入排序时元素移动步伐过小而造成性能瓶颈。而为什么要选择特定的序列，我只能简单的说，不同的序列会造成不同的性能效果。例如选择1 2 4 8 16...这一序列，那样奇数位的元素和偶数位的元素将一直得不到比较和移动。而1 4 13 ... 3n-1+1
这一序列，已经被计算科学家们证明是有效率的。
//shell排序
template<class Item>
void shellsort(Item a[],int l,int r){
int h;
for(h=1;h<=(r-1)/9;h=3*h+1); //递增序列 1 4 13... 3n-1+1
for(;h>0;h/=3)
for(int i=l+h;i<=r;i++){
int j=i;
Item v=a[i];
while(j>=l+h&&v<a[j-h]){
a[j]=a[j-h];
j-=h;
}
a[j]=v;
}
}
快速排序(quicksort)
下面我们回到现实世界，看看目前最广泛适用的排序方法：快速排序。顾名思义，它是目前发现的算法中，平均性能和适应性最好的。快速排序是一个递归算法。其基本原理是，选择一个元素v，然后进行分区操作。把待排序数组分成左右两块，左边的都比v值要小，右边的比v值大。然后再调用自身对左右两块进行排序。快速排序的核心是它的分区函数(partition)，该函数的一般实现是这样的：选择数组最后以为作为v，然后从左端起向后搜索大于v的元素，从右端起向前搜索小于v的元素，找到之后把两者交换。最后当两个搜索都到达中间分界位置时，将v交换到该位置，并返回该位置。
举例说明一下其过程。譬如要对2,8,4,9,3,5,7,6进行分区。首先选择最后元素6作为v值，然后从2开始向后搜索大于6的元素，从7开始搜索小于6的元素。第一次找到的是8,5，将它们对换；然后找到9,3，将它们对换得到2,5,4,3,9,8,7,6。接着左端搜索指针继续向后移动，它与右端搜索指针在元素9的位置相遇了。结束搜索，将v值与该位置的9交换，得到2,5,4,3,6,8,7,9，返回该位置的序号4。
基本的快速排序算法如下：
//quicksort 原型
template<class Item>
inline int partition(Item a[],int l,int r){
int i=l-1,j=r;
Item v=a[r]; //选择数组最后以为作为v
for(;;)
{
while(a[++i]<v); //向后搜索 大于v的元素
while(v<a[--j]) if(j==l) break; //向前搜索 小于v的元素
if(i>=j) break;
exch(a[i],a[j]); //交换搜索找到的元素
}
exch(a[i],a[r]); //交换v值到数组分区边界位置
return i;
}
template<class Item>
void quicksort(Item a[],int l,int r){
if(r<=l) return;
int i=partition(a,l,r);
quicksort(a,l,i-1);
quicksort(a,i+1,r);
}
快速排序的效率决定于其v值的选取，当v值刚好是数据的中值时，分区将数据平分为两块，这时效率是最高的。但是如果 v值是数据的最大或追小值附近的值时，其效率很低。所有快速排序适合于随即分布的数据，而不适合接近有序或反序的数据。另外当数据递归到规模较小的数据时，快速排序的操作由于过于烦琐，其效率反而比一般的插入排序要低。
只要解决以上问题，快速排序的效率可以大大提高。在这里使用的方法是1.选择v值时，比较首位，末位和中位，选取其中间值。这样便可以避免 v值是最大或最小值。2.当递归到较小规模的数据时，这里选择10作为临界值，直接忽略该数据。然后当完成快速排序时，在对结果进行插入排序。优化的算法如下：
//优化的quicksort
static const int sort__MINSIZE =10;
template<class Item>
inline int partition(Item a[],int l,int r){
int i=l-1,j=r;
Item v=a[r];
for(;;)
{
while(a[++i]<v);
while(v<a[--j]) if(j==l) break;
if(i>=j) break;
exch(a[i],a[j]);
}
exch(a[i],a[r]);
return i;
}
template<class Item>
void quicksort_av(Item a[],int l,int r){
if(r-l<=sort__MINSIZE) return; //忽略规模大小为sort__MINSIZE值以下数据
exch(a[(l+r)/2],a[r-1]); //比较首位,末位,和中位(l+r)/2
compexch(a[l],a[r-1]); //的元素,选择中间值作为
compexch(a[l],a[r]); //分区的v值
compexch(a[r-1],a[r]);
int i=partition(a,l+1,r-1);
quicksort_av(a,l,i-1);
quicksort_av(a,i+1,r);
}
template<class Item>
void quicksort(Item a[],int l,int r){
quicksort_av(a,l,r);
insertion(a,l,r); //最后将数据进行插入排序
}
归并排序(mergesort)
快速排序虽然效率高，但时它是不稳定的排序。例如当键值队的数据进行排序时，两个键相同的元素a,b。排序后的位置可能是 a先于b，也可能是b先于a。而排序前不能对其位值进行预计（不考虑其他元素前提下）。而这种稳定性，有时是必须保证的。下面介绍一种效率和快速排序相当，的稳定排序：归并排序。
归并排序也是一种递归算法，它将数据平分两半，然后分别对其调用归并排序，最后将其合并。它的核心操作位于其合并函数(merge) 根据不同的需要，merge函数有两种。一种是将合并的结果放到输出的数组，一种是把结果放回源数组的in-place merge。但无论哪种，都不能避免需要额外的空间来完成，这是归并排序的最大缺点。
先看看in-place merge的实现，它先把数据复制到额外的数组aux[]，然后再将它合并回源数组a[]。
//标准的mergesort
template<class Item>
void in_place_merge(Item a[],int l,int m,int r){
int i,j;
static Item aux[merge__N];
for(i=m+1;i>l;i--) aux[i-1]=a[i-1];
for(j=m;j<r;j++) aux[r+m-j]=a[j+1];
for(int k=l;k<=r;k++)
a[k]=(aux[j]<aux[i])?aux[j--]:aux[i++];
}
template<class Item>
void mergesort(Item a[],int l,int r){
if(r<=l) return;
int m=(r+l)/2;
mergesort(a,l,m);
mergesort(a,m+1,r);
in_place_merge(a,l,m,r);
}
可以从两个方面对标准的归并排序进行优化。
一是对较少规模的数据使用插入排序，其中的原因和快速排序相同。
二是用out merge 来替代in-place
merge来减少对数据的复制操作，这里的关键是交替的使用两个数组。首先对原数组进行1次完成的复制，然后在递归处理时将它们对调作为参数，最后合并时把复制数组归并会原数组。
//优化的mergesort
template<class Item>
void out_merge(Item out[],Item a[],int l,int m,int r){
int i=l,j=m+1;
while(i<=m&&j<=r)
out[l++]=(a[i]<a[j])?a[i++]:a[j++];
for(;i<=m;i++)
out[l++]=a[i];
for(;j<=r;j++)
out[l++]=a[j];
}
template<class Item>
void mergesort_av(Item a[],Item b[],int l,int r){
if(r-l<=sort__MINSIZE){
insertion(a,l,r);
return;
}
int m=(l+r)/2;
mergesort_av(b,a,l,m);
mergesort_av(b,a,m+1,r);
out_merge(a,b,l,m,r);
}
template<class Item>
void mergesort(Item a[],int l,int r){
Item* aux=new Item[r-l+1];
for(int i=l;i<=r;i++) aux[i]=a[i];
mergesort_av(a,aux,l,r);
delete [] aux;
}
插入表情