选择排序

思想

算法描述

void SelectionSort(int* a, size_t size)
{
    for (int i = 0; i < size; ++i)
    {
        int MinIndex = i;
        for (int j = i + 1; j < size; ++j)
        {
            if (a[j] < a[MinIndex])
            {
                MinIndex = j;
            }
        }
        swap(a[i], a[MinIndex]);
    }
}

优化

从两头开始比较，每次选出一个最大，同时也选出一个最小，这样效率会更高一些。

void SelectSort(int* a, size_t size, int left, int right)
{
    assert(a);
    int Left = left, Right = right;
    if (left >= right)
    {
        return;
    }
    if (a[left] > a[right])
    {
        swap(a[left], a[right]);
    }
    while (Left < Right)
    {
        if (a[Left + 1] >= a[Right - 1])
        {
            if (a[right] < a[Left + 1])
            {
                swap(a[right], a[Left + 1]);
            }
            else
            {
                --Right;
            }
            if (a[left] > a[Right - 1])
            {
                swap(a[left], a[Right - 1]);
            }
            else
            {
                ++Left;
            }
        }
        if (a[Left + 1] < a[Right - 1])
        {
            if (a[right] < a[Right - 1])
            {
                swap(a[right], a[Right - 1]);
            }
            else
            {
                --Right;
            }
            if (a[left] > a[Left + 1])
            {
                swap(a[left], a[Left + 1]);
            }
            else
            {
                ++Left;
            }
        }
    }
    SelectSort(a, size, ++left, --right);
}