直接插入排序

最近更新于 2024-05-06 07:58

环境

平台工具集：Visual Studio 2022 v143
C 语言标准：C17
字符集：Unicode

算法实现

以 6 3 9 7 5 为例，将其分为有序数组和无序数组，初始有序数组成员为原数组第一个元素
6 | 3 9 7 5

第一轮：将无序数组第一个成员 3 提出来，并和有序数组最后一个成员 6 比较，3 小于 6，则有序数组最后一个成员往后移动一位
□ 6 | 9 7 5 (3)
有序数组已到头，则将提出来的 3 插入到空位
3 6 | 9 7 5

第二轮：将无序数组第一个成员 9 提出来，将其和有序数组最后一个元素 6 比较，9 大于 6 无序移动，则不移动
3 6 9 | 7 5

第三轮：将无序数组第一个元素 7 提出来，将其和有序数组最后一个元素 9 比较， 7 小于 9，将 7 往后移动一位
3 6 □ 9 | 5 (7)
再将 7 和有序数组倒数第二个元素 6 比较，7 大于 6，则不移动，并将提出来的 7 插入空位
3 6 7 9 | 5

第四轮：将无序数组第一个元素 5 提出来和有序数组最后一个元素 9 比较，5 小于 9，9 后移一位
3 6 7 □ 9 (5)
再将 5 和有序数组倒数第二个元素 7 比较，5 小于 7，7 后移一位
3 6 □ 7 9 (5)
再将 5 和有序数组倒数第三个元素 6 比较，5 小于 6，6 后移一位
3 □ 6 7 9 (5)
再将 5 和有序数组倒数第四个元素比较，5 大于 3，不移动，将提出来的 5 插入空位
3 5 6 7 9

时间复杂度为 O(n^2)，稳定的排序算法

void sort(int array[], int n)
{
    for (int j, i = 1; i < n; ++i)
    {
        int tmp = array[i];
        for (j = i - 1; j >= 0 && tmp < array[j]; --j)
        {
                array[j + 1] = array[j];
        }
        array[j + 1] = tmp;
    }
}