【算法】选择排序

选择排序概述

从1-N，循环遍历，每次从剩下的序列中选择最大或者最小的元素放到剩下序列的前一个。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

1. 初始状态：无序区为R[1…n]，有序区为空。
2. 第1趟排序
   在无序区R[1…n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1…1]和R[2…n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
   ……
3. 第i趟排序
   第i趟排序开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

代码实现：

std::vector<int> v;

//选择排序
template<class ForwardIt>
void selection_sort(ForwardIt begin, ForwardIt end)
{
    for (ForwardIt i = begin; i != end; ++i)
    {
        cout << *i << "  swap  " << *std::min_element(i, end) << endl;
        std::iter_swap(i, std::min_element(i, end));            //每次从剩下序列中取出最小的元素
        print(v);
    }
}

//打印数据
void print(std::vector<int> v)
{
    for (auto e : v) std::cout << e << " ";
    cout << endl;
}

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(-10, 10);
    generate_n(back_inserter(v), 20, bind(dist, gen));  //初始化随机数

    std::cout << "Before sort: ";
    print(v);

    selection_sort(v.begin(), v.end());

    std::cout << "\nAfter sort: ";
    print(v);

    getchar();
}

根据打印信息我们可以清楚的看到选择排序的过程。