数据结构 ——— 直接插入排序算法的实现
目录
直接插入排序算法的思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中
直到所有的记录插入完为止，得到一个新的有序序列
在实际中，玩扑克牌时，就是使用的直接插入排序的思想
代码实现（默认排升序）
代码演示：
void InsertSort(int* a, int size)
{
for (int i = 1; i < size; i++)
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}代码解析：
指针 a 是指向需要排序的数组的首元素
size 是数组元素的总个数
变量 end 为数组元素的下标，a[end] 包括 a[end] 之前的元素都是有序的，所以最开始有序的只有第一个元素
tmp 为待插入为有序的元素，也就是 a[end] 后面的一个元素
while 循环的作用是当 a[end] 大于 tmp 时，那么就把 a[end] 放在 a[end+1] 的位置，也就是往后挪动，不用担心会覆盖数据，因为 tmp 就是被覆盖的数据
只要当 end 不大于或者等于 0 时，也就是表示要插入的 tmp 比 a[end] 之前的值都小，end 就会一直递减到 -1，就会跳出循环
或者当 a[end] 不大于 tmp 时，也就是 tmp 等于或者小于 a[end] 时，也会走到 break ，跳出循环
这时候 tmp 插入到 a[end + 1] 的位置，也就是 tmp 应该排序的最终位置
以上的 while 排序是完成一个元素排到最终改走的位置，也就是单躺排序
要想实现所有元素排好序，那就利用 for 循环，控制 end 和 tmp 变量
for 循环从第二个元素的下标开始遍历，i 代表的是第二个元素的下标
end 从 0 开始，依次往后递增，tmp 从第二个元素开始，依次往后遍历
当 tmp 为数组最后一个元素时，通过 while 循环排序后，数组就有序了，且 for 循环也就走完了
代码验证：
小结：
先实现单趟排序的思想，再实现排序整个数组的思想
原文地址：https://blog.csdn.net/weixin_55341642/article/details/143854984
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！