【算法】直接插入排序解析

​

活动地址：CSDN21天学习挑战赛

作者：柒号华仔
个人主页：欢迎访问我的主页
个人信条：星光不问赶路人,岁月不负有心人。
个人方向：主要方向为5G，同时兼顾其他网络协议，编解码协议，C/C++，linux，云原生等，感兴趣的小伙伴可以关注我，一起交流。
推荐一款模拟面试、刷题神器： 👉 登录免费刷题

目录

• • 1. 直接插入排序介绍
  • • 1.1 定义
    • 1.2 基本原理
    • 1.3 时间复杂度
    • 1.4 空间复杂度
    • 1.5 优缺点
  • 2. 代码实现
  • • 2.1 代码设计
    • 2.2 代码实现

1. 直接插入排序介绍

1.1 定义

直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

1.2 基本原理

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
下面的动图非常清晰的诠释了直接插入排序的过程：

1.3 时间复杂度

时间复杂度
最好的情况是数组所有元素已经是有序排列，在排序时待排元素只需与前一元素比较，不用继续往前搜索比较，时间复杂度为O(n)；
最差的情况是数组所有元素全部反序，在排序时待排元素需要与前面所有有序元素进行比较，比较次数为：
1+2+…+(n-1) = n(n-1)/2
每次前面的有序元素均要往后移动，移动次数为：
（1+2)+(2+2)+…+(n-1+2) =(n-1)(n+4)/2
综上所述，直接插入排序的平均时间复杂度为O( n 2 n^2 n2) 。

1.4 空间复杂度

直接插入排序为平行移动，因此空间复杂度为：O(1) 。

1.5 优缺点

优点：直接插入排序算法简单，当待排序记录数量n很小时，局部有序时，较为适用。
缺点：当数据量庞大并且乱序严重时，比较和移动次数多，排序效率低。

2. 代码实现

2.1 代码设计

a. 实现直接插入排序需要设计两层循环，整个数组为外循环，已经排列好的有序元素为内循环；
b. 从外循环取出待排元素array[i]，使用临时变量temp存储其值；
c. 将待排元素与内循环的有序元素依次（从后往前）进行比较，若有序元素比待排元素大，则向后移动一位；
d. 直至有序元素比待排元素小，则不再移动，将temp赋值给array[j+1]。

2.2 代码实现

#include   void printArray(int array[], int size) {    int i;    for (i = 0; i < size; i++) { printf("%d ", array[i]);    }    printf("\n");}void insertSort(int array[], int size) {    int temp,i,j;    for (i = 1; i < size; i++) { temp = array[i]; j = i-1; while (j >= 0 && array[j] > temp) {     array[j+1] = array[j];     j--; } array[j+1] = temp; printArray(array, size);    }}int main() {    int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};    printArray(array, sizeof(array)/sizeof(int));    insertSort(array, sizeof(array)/sizeof(int));    return 0;}

运行结果：

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
3 38 44 5 47 15 36 26 27 2 46 4 19 50 48
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48
3 5 15 38 44 47 36 26 27 2 46 4 19 50 48
3 5 15 36 38 44 47 26 27 2 46 4 19 50 48
3 5 15 26 36 38 44 47 27 2 46 4 19 50 48
3 5 15 26 27 36 38 44 47 2 46 4 19 50 48
2 3 5 15 26 27 36 38 44 47 46 4 19 50 48
2 3 5 15 26 27 36 38 44 46 47 4 19 50 48
2 3 4 5 15 26 27 36 38 44 46 47 19 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

K歌软件