希尔排序

3

数据

  • 平均时间复杂度：O(nlogn)

  • 最好时间复杂度：O(nlog^2n)

  • 最坏时间复杂度：O(nlog^2n)

  • 空间复杂度：O(1)

  • 排序方式：In-Place

  • 稳定性：不稳定

描述

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

动图

C#实现

public class ShellSort
{
    public static void Sort<T>(IList<T> list, Func<T, T, bool> compare)
    {
        if (list.Count < 2)
        {
            return;
        }

        for (int step = list.Count / 2; step >= 1; step /= 2)
        {
            for (int i = step; i < list.Count; i += step)
            {
                var checkIndex = i;
                for (int j = i - step; j >= 0; j -= step)
                {
                    if (compare(list[checkIndex], list[j]))
                    {
                        SortHelper.Exchange(list, checkIndex, j);
                        checkIndex = j;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    }
}

Lua实现

function ShellSort(list, compareFunc)
    local count = #list
    if count < 2 then
        return
    end
    
    local step = math.floor(count / 2)
    while step >= 1 do
        for i = step + 1, count, step do
            local checkIndex = i
            for j = i - step, 1, -step do
                if compareFunc(list[checkIndex], list[j])  then
                    Exchange(list, checkIndex, j)
                    checkIndex = j
                else
                    break
                end
            end
        end
        step = math.floor(step / 2)
    end
    
end