希尔排序:可以认为是插入排序的优化版本,是缩小增量排序,对数组按照增量进行分组,然后对每个分组分别进行插入排序,缩小增量,重复上述操作直到增量小于1。

特点

原地排序,算法的具体效率取决于增量和具体的数据个数,具体的实现也比较简单

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过(效率还行
XEsort_1

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    //增量
    *returnSize = numsSize;
    size_t x = numsSize / 2;
    int Med = 0;
    while (x >= 1)    //增量为1跳出循环
    {
        for (size_t i = 0; i < x; i++)        //分割多个组
        {
            //插入排序
            for (size_t j = i; j < numsSize; j += x)        //插入各个元素
            {
                Med = nums[j];
                size_t k = j;
                while (k > i&& Med < nums[k - x])
                {
                    nums[k] = nums[k - x];
                    k -= x;
                }
                nums[k] = Med;
            }
        }
        x /= 2;
    }
    return nums;
}

C++实现

Leetcode上917.排序数组中测试通过(效率还行
XEsort_2

vector<int> sortArray(vector<int>& nums)
{
    //增量
    size_t x = nums.size() / 2;
    int Med = 0;
    while (x >= 1)    //增量为1跳出循环
    {
        for (size_t i = 0; i < x; i++)        //分割多个组
        {
            //插入排序
            for (size_t j = i; j < nums.size(); j += x)        //插入各个元素
            {
                Med = nums[j];
                size_t k = j;
                while (k > i&& Med < nums[k - x])
                {
                    nums[k] = nums[k - x];
                    k -= x;
                }
                nums[k] = Med;
            }
        }
        x /= 2;
    }
    return nums;
}
Last modification:April 15th, 2020 at 09:11 am