数据结构-选择排序以及对它的优化

1. 选择排序
   八大排序算法之一的选择排序，它的原理是比较容易理解的。
   每一趟遍历都在后面元素中找到最小的元素（升序）,记录它的下标，一趟走完后，如果记录的元素下标不等于这组元素第一个元素则进行交换。
   我们可以配合图来看:
   

还另外加了升序和降序的仿函数，这样可以更加实用一些
下面是实现代码:

template<class T>
struct Less
{
    bool operator()(const T& s, const T& l)
    {
        return s < l;
    }
};
template<class T>
struct Greater
{
    bool operator()(const T&s, const T& l)
    {
        return s > l;
    }
};
using namespace std;
template<class T = int, class Compare = Greater<T>>
void SelectSort(T* arr,int size)
{
    Compare com;
    for (int i = 0; i < size - 1; i++)
    {
        int k = i;
        for (int j = i + 1; j < size; j++)
        {
            if (com(arr[k], arr[j]))
                k = j;
        }
        if (k != i)
            std::swap(arr[i], arr[k]);
    }
}
void SelectTest()
{
    int arr[] = { 3, 4, 1, 5, 2 };
    SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
}

这样最基本的选择排序就出来了，但是仔细想想我们一次选一个最小的数进行交换，那我们为什么不能每趟遍历选出最大和最小的，最大的和最后交换，最小的和前面交换，这样效率会更高一些，这样想，于是对代码进行优化改良，就有了下面优化版本的选择排序。

2. 选择排序优化

using namespace std;
template<class T>
struct Less
{
    bool operator()(const T& s, const T& l)
    {
        return s < l;
    }
};
template<class T>
struct Greater
{
    bool operator()(ctonst T&s, const T& l)
    {
        return s > l;
    }
};

template<class T = int, class Compare = Greater<T>>

void SelectSort(T* arr, int size)
{
    Compare com;
    int left = 0;
    int right = size - 1;
    for (; left <= right;left++,right--)
    {
        int min = left;
        int max = right;
        for (int i = left; i <= right; i++)
        {
            if (com(arr[min],arr[i]))
                min = i;
            if (com(arr[i],arr[max]))
                max = i;
        }
        swap(arr[max], arr[right]);
        if (min == right)
            min = max;
        swap(arr[min], arr[left]);
    }
}
void SelectTest()
{
    int arr[] = { 3, 4, 1, 5, 2 };
    SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
}

最后，分析一下选择排序的时间复杂度，选择排序的时间复杂度是O（n^2）。
因为需要选择，所以无论什么情况都是要把为排序序列完整的遍历一遍才可以，所以选择排序的时间复杂度最好的时候也是O（n^2）。