插入排序:即将待排序数组的元素按照顺序一个一个插入新数组

特点

该算法依然需要维护两个数组,一个待排序,一个有序。每次从待排序数组顺序的取出一个元素,按顺序插入到有序数组中,因此有一个新的元素与有序数组中元素的比较。
注意:该算法主要在插入的开销较大,因为以顺序数组来说,插入元素将涉及到大量的元素移动,如果是链表相对来讲开销比较小

以递增排序为例


C语言实现

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

该实现中需要调用者自己释放返回的数组指针所指向的内存

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int* outA = (int*)calloc(numsSize, sizeof(int));
    *returnSize = numsSize;
    //注意要释放内内存,否则会内存泄漏
    if (outA == 0)
    {
        return 0;
    }
    memset(outA, 0, numsSize * sizeof(int));

    outA[0] = nums[0];
    size_t outAlen = 1;
    for (size_t i = 1; i < numsSize; i++)
    {
        size_t j;
        for (j = outAlen; j >= 1; j--)
        {
            if (nums[i] < outA[j - 1])
            {
                outA[j] = outA[j - 1];
            }
            else
            {                
                break;
            }
        }
        outA[j] = nums[i];
        outAlen++;
    }
    return outA;
}

C++实现

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

vector<int> sortArray(vector<int>& nums)
{
    size_t inAlen = nums.size();
    vector<int> outA;
    outA.push_back(nums[0]);

    for (size_t i = 1; i < inAlen; i++)
    {
        size_t j;
        for (j = outA.size(); j >= 1; j--)
        {
            if (nums[i] >= outA[j - 1])
            {
                break;
            }
        }
        outA.insert(outA.begin() + j, nums[i]);
    }

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