直接插入排序算法——C/C++

╰+攻爆jí腚メ 2022-10-01 11:47 122阅读 0赞

# 直接插入排序 #

## 1. 插入排序（Insertion-Sort） ##

每次将一个待排序的数据按照大小插入到前面已经排好序的适当位置，直到全部数据插入完成为止。

## 2. 插入排序的步骤 ##

2.1、建立一个哨兵（即临时变量），把要插入的数据赋给它。
    2.2、插入数据从后面开始比较，如果大于前面的就记录下标，并将数据后移，直到插入数据碰到比它小的。
    2.3、将临时变量赋值给当前记录下标。
    2.4、for循环即完成全部数据插入。

## 3. 插入排序动图演示 ##

![在这里插入图片描述][6d867acd56e40fb32975f9e91d041fa9.png]

## 4. 完整代码 ##

#include <stdio.h>
    
    void display(int array[], int size) {
        
        for (int i = 0; i < size; i++) {
        
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    void InsertSort(int array[], int size) {
        
        for (int i = 1; i < size; i++) {
                // 第 1 个数肯定是有序的，从第 2 个数开始遍历，依次插入有序序列
            int temp = array[i];                // 取出第 i 个数，和前 i-1 个数比较后，插入合适位置
            int j    = i - 1;                   // 因为前 i-1 个数都是从小到大的有序序列，所以只要当前比较的数 (array[j]) 比 temp 大，就把这个数后移一位
            while (j >= 0 && array[j] > temp) {
         // 当 j < 0 或 array[j] < temp(array[i]) 时终止
                array[j + 1] = array[j];        // 将大于 temp(array[i]) 的数据后移
                j--;                            // 向前比较
            }                                   // 结束循环
            array[j + 1] = temp;                // array[i]插入到正确的位置上
    
            //打印每次排序结果
            display(array, size);
        }
    }
    
    int main() {
        
        int array[] = {
        49, 38, 65, 97, 76, 13, 27, 49, 10};
        int size    = sizeof(array) / sizeof(int);
    
        //打印原始数据
        printf("%d \n", size);
        display(array, size);
        InsertSort(array, size);
        return 0;
    }

## 5. 结果展示 ##

（显示每一次插入信息）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 6. 算法分析 ##

时间复杂度：平均O(n^2)，最好O(n)， 最坏O(n^2)  
空间复杂度：O(1)  
稳定性：稳定

[6d867acd56e40fb32975f9e91d041fa9.png]: /images/20220118/0209f9c44811428b8fb27894dc51a5fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20220118/c090c13888bc43c9a81710ce55f1be97.png