第一节似乎写的字太多了，这一节让我们直接开始正文。

选择排序

选择排序，算法如其名，就是“选择一个最小（最大）的放到合适的位置”。

所以，让我们大致描述一下算法的流程：

1.从所有位置中选择一个位置，当作要交换的位置。和插入排序有些不同，Insert选择的是要交换的数，而选择则选择的是要被排好的位置。什么意思呢，就是当我们选择位置==0时，我们要的结果是一个放在此位置的数，即最小值或最大值。所以，我们应该选作比较的量，是位置。

2.在内部循环中，我们遍历所有的数，找到最小的，放在此位置。
注意：1）每次都不能选拍好的位置上的数重新比较。
2）最后一个“数”不用比较，其实是前面的位置都排好以后，最后的位置也就固定了。

假设我们要求的是升序序列，则算法如下：

template <typename T>
void SelectSort( T A[ ], int N )
{
    for( i = N - 1; i > 0; --i )
    {
        int tmp = i;  //将第i个位置暂时设为tmp，用做比较
        for( int j = 0; j < i; ++j )
            if( A[ j ] < A[ tmp ])
                tmp = j;
        swap( &A[ i ], &A[ tmp ]);  //最后那个最小的和本次循环的位置（i）进行交换
}

“注意”的第一条反映在代码中就是：for( j = N - 1; j > i; --j)而不是for( j = N - 1; j > 0; --j)，为啥不能拿选好的位置重新比较呢？想一想就知道啦，选好的已经是最小的了，你拿这个比，不就是拿最小的去比，相当于把最小的又放到了其他位置说啦。

此处需要有个交换的函数，只要学过大一“c语言程序设计”的同学们，就一定知道，你们的老师肯定在这里说过很多遍，“交换的时候要用指针啦，因为只有指针传递才能真的交换，值传递出了作用域是没用的啦”，那么我们先把使用指针传递的函数写出来吧：

template <typename T>
void swap( T *a, T *b )
{
    auto tmp = *a;
    *a = *b;
    *b = tmp;
}

首先，这代码是正确的；那么，老师说的话是正确的吗？其实，c语言只有值传递，c++只有值传递和引用传递。他们都没有“指针传递”。那么为什么用指针就行了呢，因为我们在做swap()时，具体操作是：swap( &A[ i ], &A[ tmp ]);，也就是说，我们赋给swap()函数的是A[ i ]和A [ tmp ]的地址，swap()接受的也依旧是2个地址的拷贝，我们并没有改变2个地址，改变的是地址指向的对象。更贴近硬件层面的说，通过传递指针的拷贝，我们改变了指针所代表的地址（指针的值就是地址啦~）所指向的值，而这个值则是直接存在于一片内存空间中，于是我们越过了改变地址而直接改变值的内存情况。那么，什么是改变地址呢？

template <typename T>
void swap( *a, *b )
{
    int *tmp = a;
    a = b;
    b = tmp;
}

这就是直接改变地址的写法。很明显，此算法是无效的。把地址当作形参传递后改变地址，最后并不会改变实参中地址的情况。

那么，有没有其他写法呢？当然有，用引用传递。c++中，引用就是变量的别名。在很多语言中，赋值语句已经是默认引用传递了，很多时候为了寻找拷贝，必须得使用一下名为“.copy()”的方法。那么，我们用引用实现一下swap()：

template <typename T>
void swap( T &a,  T &b )
{
    auto tmp = a;
    a = b;
    b = tmp;
}

这时，调用swap也相应的变味为了swap(A[i], A[tmp]);，引用传递的好处是不必拷贝，剩下了不少内存~~（同时代码也似乎看得懂了，不是吗！！！）一个需要注意的是，这个时候不要using namespace std;，因为会自动引入系统中的swap，这时编译器就不知道要重载哪个函数了。

希尔排序（shell sort）

话不多说，我们直接看看希尔排序吧。之前我就想把希尔和插入放在一节，因为希尔排序在实现的时候其实就是间隔不同的插入排序。

我们假设间隔取N/2，且每次间隔缩小一半：

template <typename T>
void ShellSort(T A[ ], int N)
{
    int i, j, Increment;  //Increment是增量，就是间隔;i 控制插入排序中的要插入的元素；j控制比较和交换
    T tmp;
    for( Increment = N / 2; Increment > 0; Increment /= 2)
        //下边的就是插入排序，不是吗？
        for( i = Increment; i < N; ++i)
        {
            tmp = A[ i ];
            for( j = i; j >= Increment  && tmp < A[ j - Increment ]; j -= Increment)
                A[ j ] = A[ j - Increment ];
            A[ j ] = tmp;
         }
}

增量不一定要取Increment = Increment / 2，准确地说，不应当取这个，如Hibbard增量：2^{k-1,k=0...~效果更好。而Sedgewick增量更更好：9*4}i-92^i+1或者4i-32^i+1。

希尔排序的时间复杂度为亚二次，也就是说，增量选取不同，其从O(N^{2)到O(N)不等（当然，到不了O(N)）。一般的，能达到O(N}3/2)。

那么我们下次就聊聊归并排序，以及归并背后的思想和各种时间复杂度证明方法。