选择排序

一、简单选择排序

选择排序每次遍历数组时，从数组中未排序部分中选择出最大（最小）元素，并将该元素与未排序部分的最后一个（第一个）元素交换，最后得到有序数组

void selection(vector<int>& nums)
{
    int min_i = 0;
    int size = nums.size();
    for (int i = 0; i < size - 1; i++)
    {
        min_i = i;
        //选出最小值
        for (int j = i + 1; j < size; j++)
        {
            if (nums[j] < nums[min_i])
                min_i = j;
        }
        //将未排序部分的第一个元素与最小元素交换
        swap(nums, i, min_i);
    }
}

二、优化

1. 一次遍历，双向选择

//二元选择排序
void select_sort( vector<int>& nums )
{
    int mini; 
    int maxi;
    for ( int i = 0; i < size/2; i++ )
    {
        mini = i;
        maxi = i;
        for ( int j = i+1; j < size-i; j++ )
        {
            if ( nums[j] < nums[mini] )
                mini = j;
            else if ( nums[j] > nums[maxi] )
                maxi = j;
        }
        if ( mini != i )
            swap( nums[i], nums[mini] );
        if ( maxi != i && maxi != j )
            swap( nums[j-1], nums[maxi] );
    }
}

三、性能分析

• 时间复杂度：O(N²)
• 空间复杂度：O(1)
• 稳定性：不稳定
• 排序方式：原地排序