挑战程序设计竞赛选读-选择排序

初等排序

选择排序

选择排序的基本思想是，在未排序序列中找到最小的那个元素，然后将它与未排序序列的首元素交换，如此以来，整个序列便逐渐归于有序。

正确性：其正确性显而易见。

复杂度：在排序过程中，主要耗时在寻找待排序列的最小元素上，且若待排序列元素个数为$N$ ，则每次需进行$N-1,N-2,\dots ,1$次比较，总的时间复杂度为
$$N-1+N-2+\cdots +1=\frac{N(N-1)}{2}=O(N^2)$$
即选择排序的时间复杂度也为$O(N^2)$级。

排序图解：

C++实现：

void selectSort(vector<int> &a)
{
    size_t length = a.size();
    for(size_t i = 0;i < length-1;i++)
    {
        int v = a[i];
        int min_v = v; //记录最小值，并把它初始化为未派序列的第一个元素
        int min_l = i; //记录最小值所在位置
        for(size_t j = i;j < length;j++)
        {
            if(min_v > a[j])
            {
                min_v = a[j];
                min_l = j;
            }
        }
        a[i] = min_v;
        a[min_l] = v;
        trace(a);
    }
}

C++实现（利用STL）：

void selectSort_STL(vector<int> &a)
{
    for(auto i = a.begin();i!=a.end();++i)
    {  
        size_t min_l;
        for(auto j = i;j!=a.end();++j)
        {
            auto min = min_element(i,a.end());
            min_l = distance(a.begin(),min);
        }
        swap(*i,a[min_l]);
        trace(a);
    }
}

rust实现（待更新）: