Algorithms

1. 排序

1.1 选择排序(selection Sort)

算法:

找到数组中最小的元素;
将它和数组的第一个元素交换位置;
在剩下的元素中找到最小元素;
将它与数组的第二个元素交换位置;
往复，直到将整个数组排序；

选择排序有两个鲜明的特点；1. 运行时间和输入无关，为了找到最小的元素而扫描一遍数组并不能为下次扫描提供什么信息，不能有效利用数组的初始状态，一个已经排序的数组和没有排序的数组用时一样长；2. 数据移动次数少：每次都会改变两个元素的值，因此只用了 N 次交换，也就是交换次数和数组的大小是线性的关系。

void selection_sort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
    if ( first == last ) return;
    for (; first != last; ++first ) {
        auto min_iter = first;
        for ( auto cur = min_iter + 1; cur != last; ++cur )
            if ( *cur < *min_iter ) min_iter = cur;
        std::iter_swap(first, min_iter);
    }
}

1.2 插入排序(Insertion Sort)

和选择排序不同，插入排序所需要的时间取决于输入元素的顺序，对于一个已经接近有序的数组的排序会比对一个随机数组或者是逆序数组排序快的多。一般来说部分有序的数组指的就是数组中逆序对比较少(事实上，插入排序需要交换的次数就等于数组中逆序数，因为交换一次就是减少了一对逆序)，比如数组每个元素距离最终位置都不远，大的有序数组接一个小的无序数组或者数组只有几个元素位置不正确，在这些情况下，插入排序的表现都很好，很可能比其他的算法都要快，同时也很适合小规模数据，这也是为什么 STL 在实现 sort() 时选择了插入排序。

void insertion_sort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
    for ( auto cur = first + 1; cur != last; ++cur ) {
        for ( auto j = cur; j > first && *j < *(j - 1); --j )
            std::iter_swap(j - 1, j);
    }
}

插入排序优化：在内循环不是每次都交换两个元素，而是将较大的元素都向右移动：

1.3 希尔排序(Shell Sort)

希尔排序是插入排序更加高效的版本，是针对插入排序的两个性质：1. 插入排序对部分有序数据效率高；2. 插入排序在一般情况下（大规模、乱序的数据）是低效的，因为每次只将数据移动一位，只能一点一点将数据从一头移动到另一头。希尔排序为了加速插入排序，做出的改进就是可以交换不相邻元素，对局部的数据进行排序，最终（步长为1）用插入排序将局部有序的数据排序。
希尔排序的思想：使数组任意间隔 h 的元素都是有序的，如果 h 很大，就可以轻易将数据移动到很远的地方（相较于普通插入排序一次只移动一位），就可以为后面使用插入排序创造条件。事实上在希尔排序中，步长的选择是很重要的部分，只要最后的步长是1（也就是插入排序），希尔排序都可以工作，而已知的有不同的步长的选择，也有不同的最坏时间复杂度。一般来说，希尔排序要比选择排序和插入排序要快，甚至在一些小的数据量中，表现比快排还好，但是在涉及大数据量时，希尔排序还是比快排慢。

void  shell_sort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
    int len = last - first, h = 1;
    while ( h < len / 3 ) h = 3 * h - 1; // 步长 h : 1, 4, 13, 121, ...
    while ( h >= 1 ) { // 间隔 h 有序
        for ( int i = h; i < len; ++i ) {
            for ( int j = i; j >= h && *(first + j) < *(first + j - h); j -= h) {
                std::iter_swap(first + j, first + j - h);
            }
        }
        h = h / 3;
    }
}

1.4 归并排序(Merge Sort)

归并：将两个有序数组归并成一个更大的有序数组。