选择排序:顾名思义每次选择一个最大/最小的数放到一个新的数组中,重复此过程,当所有的数都放入新数组的时候,排序完成

特点

选择排序算法需要维护两个数组,一个是有序数组,一个待排序数组,每次选择待排序数组的一个最小数填入有序数组的后面,直到待排序数组为空
注意:该算法最重要的是需要解决如何判断一个待排序的数组中的某个元素是否已经加入有序数组。

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过但超时(效率比较低...
XZsort_1

这个C语言实现通过传入的inA指针修改了原数组的数据 PS: 通过INT_MAX的值认为该元素已经排入有序数组

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int* outA = (int*)calloc(numsSize, 4);
    *returnSize = numsSize;
    if (outA == 0)
    {
        return 0;
    }
    memset(outA, 0, numsSize * 4);

    //将数组中的值为INT_MAX的元素排到有序数组最后
    for (size_t i = 0, j = numsSize - 1; i < numsSize; i++)
    {
        if (nums[i] == INT_MAX)
        {
            outA[j] = INT_MAX;
            j--;
        }
    }

    struct DAT
    {
        int v;        //值
        int x;    //下标
    };

    for (size_t i = 0; i < numsSize; i++)
    {
        //查找最小值
        struct DAT add;
        add.v=INT_MAX;
        add.x=INT_MIN;

        for (size_t j = 0; j < numsSize; j++)
        {            
            if (nums[j] < INT_MAX)
            {
                if (nums[j] <= add.v)
                {
                    add.v = nums[j];
                    add.x = j;
                }
            }
        }
        if (add.x == INT_MIN)
        {
            return outA;
        }
        outA[i] = add.v;
        nums[add.x] = INT_MAX;
    }
    
    return outA;
}

C++实现

Leetcode上917.排序数组中测试通过依旧超时(效率比较低...
XZsort_2

vector<int> sortArray(vector<int>& nums) 
{
    vector<int> outA;

    struct DAT
    {
        int v;        //值
        size_t x;    //下标
    };

    while (!nums.empty())
    {
        size_t max = nums.size();
        //查找最小的元素
        struct DAT add{ nums[0],0 };
        for (size_t i = 1; i < max; i++)
        {
            if (nums[i] <= add.v)
            {
                add.v = nums[i];
                add.x = i;
            }
        }

        nums.erase(nums.begin() + add.x);
        outA.push_back(add.v);    
    }

    return outA;
}
Last modification:April 15th, 2020 at 09:12 am