排序算法——直接插入排序详细讲解
目录
一、排序算法的类型、稳定性及复杂度
判断稳定的标准
排序前后，相同值的相对位置改不改变
改变：不稳定
不改变：稳定
二、排序原理
将需要排序的值依次插入到一个已经排好序的序列中，直到所有的值插入完毕
单次排序
首先我们要理解单次排序的过程
- 将需要排序的值记录下来，并将有序序列最后一个数的位置记录下来
tmp向前遍历比较，如果比较的数比tmp大，那么这个位置向后移动一位，并更新比较的位置，当比较的数等于或小于tmp，将tmp插入到这个数的后面，具体实现逻辑图如下：
- tmp的值和end所在位置的值6进行比较
- end所在位置的值比tmp大，所以end位置的值向后移动一位，将4覆盖，这就是为什么要将插入的数记录起来的原因，然后将end更新，tmp继续和end所在位置的值进行比较
- end所在位置的值比tmp大，所以end位置的值向后移动一位，将5覆盖,将end更新，tmp继续和end所在位置的值进行比较
- end所在位置的值比tmp小，将tmp的值插入进end+1的位置，单次插入完成
多次排序
理解了单次排次，多次排序就很容易了，只需要利用循环将需要插入的数依次插入，直到需要排序的序列全部插入，代码如下
三、代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("->%d", a[i]);
}
printf("\n");
}
//直接插入排序
void InsertSort(int* a, int n)
{
int i = 0;
//外层循环
for (i = 0; i < n - 1; i++)
{
//单次排序
int end = i;
int tmp = a[i + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
int main()
{
//直接插入排序
int arr[] = { 2,5,7,4,2,8,1,43,7,2,1,7 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("原序列顺序为：");
Print(arr, size);
InsertSort(arr, size);
printf("插入排序后顺序为：");
Print(arr, size);
return 0;
}四、时间复杂度 （排升序）
最好情况：O(N)
本来就有序的时候，只需要遍历一遍就可以
最坏情况：O(N^2)
当序列是逆序时是最坏的情况
平均情况：O(N^2)
五、空间复杂度
开辟空间为常量，所以空间复杂度为O(1)
原文地址：https://blog.csdn.net/Xiaodao12345djs/article/details/143635293
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！