Sort

#include <assert.h>

void InsertSort(int* array, int size)
{
    assert(array);

    // 遍历未排序的部分
    for (int sortedEndIndex = 0; sortedEndIndex < size - 1; ++sortedEndIndex) // 已排序部分的最后一个下标
    {
        int unsortedElement = array[sortedEndIndex + 1]; // 需要插入到已排序部分的元素
        int currentIndex = sortedEndIndex; // 当前比较的已排序元素下标

        // 单趟插入过程：从已排序部分的末尾向前遍历
        while (currentIndex >= 0 && array[currentIndex] > unsortedElement)
        {
            array[currentIndex + 1] = array[currentIndex]; // 将较大的已排序元素向后移动
            --currentIndex; // 向前比较
        }

        // 将未排序元素插入到正确位置
        array[currentIndex + 1] = unsortedElement;
    }
}

#include <assert.h>

void ShellSort(int* array, int size)
{
    assert(array);

    int gap = size; // 初始化间隔

    // 不断缩小间隔，直到间隔为 1
    while (gap > 1)
    {
        // 缩小间隔的策略，可以使用 gap /= 2 或 gap = gap / 3 + 1
        gap = gap / 3 + 1;

        // 对每组间隔为 gap 的子数组进行插入排序
        for (int i = 0; i < size - gap; ++i)
        {
            int sortedEndIndex = i; // 已排序部分的最后一个下标
            int unsortedElement = array[sortedEndIndex + gap]; // 需要插入的元素

            // 在当前组内从后向前插入排序
            while (sortedEndIndex >= 0 && array[sortedEndIndex] > unsortedElement)
            {
                array[sortedEndIndex + gap] = array[sortedEndIndex]; // 向后移动较大元素
                sortedEndIndex -= gap; // 按间隔向前比较
            }

            // 插入未排序元素到正确位置
            array[sortedEndIndex + gap] = unsortedElement;
        }
    }
}