直接插入排序

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

Table of Contents

环境

平台工具集: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;
    }
}

file

直接插入排序
Scroll to top