选择排序 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki

从今天开始，重启久违的数据结构与算法之道！虽然如今学生时代早就落幕，但关键是初衷与快乐。最近刚学 Python 得差不多了，也不急于参与开源项目。就用 Python 重新实现一遍玩玩吧，也是挖掘 Python 特性的好机会。

意外地，我在本维基上没找到对选择排序的 C++ 实现解说，但现在的重点是 Python, 于是在这里只贴代码了事：

#ifndef SELECTION_SORT_H_
#define SELECTION_SORT_H_

#include <algorithm>

template <typename ForwardIterator>
void SelectionSort(
    ForwardIterator first,
    ForwardIterator last) {
  for (auto iterator = first; iterator != last; ++iterator)
    std::iter_swap(iterator, std::min_element(iterator, last));
}

#endif // SELECTION_SORT_H_

我发现，Python 不愧是动态语言，泛型天生就大显神威。我们不用关心传入的参数是什么，只要它真如同 sequence 字面上的意思，即和 built-in sequence type 一样，可索引可切片等：

def selection_sort(sequence):
    for index, element in enumerate(sequence):
        min_element = min(sequence[index:])
        min_index = sequence.index(min_element)
        sequence[index], sequence[min_index] = min_element, element

此外用到的特性还有 enumerate, 可以同时返回索引值和对应的值，话说现在看来 C++ 的 iterator 抽象更胜一筹，毕竟可以表示迭代又表示对应的值（只需加 * 前缀）；接着用泛型函数 min 和 sequence 类型方法 index 可以得到 min_element 和 min_index; 最后是 Pythonic 的 swap 了。

PS: 我发现模块名居然不能包含划线符。