插入排序和希尔排序
目录
前言
我们应该学习过冒泡排序，排序的方式是有很多的，所以我们可以学习更多更为有效的排序。
一.插入排序的实现原理
我们先用一个动态图来理解插入排序的实现原理：
如图所示，插入排序就是从第二个数开始，如果要进行升序排序的话，之前的数比它要大就将其向后推进直到这个数比它要小才结束将其插入到其中。由于之前排序的数已经有序了，所以直接插入后并不会打乱有序。
二.代码实现
从第二个开始向前比较，将这个数保存到tmp上，将之前的数的下标保存为end，嵌套循环如果没有找到的话就将end的值向后推进赋值到end+1的位置，将end递减后继续执行，循环的结束条件为end下标小于0或找到了这个插入的位置，最后就完成实现。
void Insertsort(int* a, int n)
{
int i = 0;
for (i = 1; i < n; 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;
}
}三.理解希尔排序
插入排序的效率我们可以通过特殊的方式使其的效率进一步优化，我们将每一个数都进行相应的比较，这样做的话效率就并没有什么提升，我们可以将其先进行大概的排序，通过设置一个间隙值来约束范围，通过这样的话，就可以减少执行次数实现排序，这种排序就被叫做希尔排序。
四.代码实现
与之前的插入排序有着许多的相同之处，希尔排序需要设置一个gap间隙用来约束，我们可以用排序数量的二分之一来表示最开始的gap，每循环一次变为原来的二分之一，这个时候的end就变为了i-gap了，因为之前的插入排序相当于间隙gap为1，所以end为i-1，还是结束标志就为end小于0或者找到了可以将数插入的位置，希尔排序的时间复杂度为O(N*logN)。
#include<stdio.h>
void shellsort(int* a, int n)
{
int gap = n;
while(gap>1)
{
gap /= 2;
int i = 0;
for (i = gap; i < n; i ++)
{
int end = i - gap;
int tmp = a[i];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
总结
我们有着很多的排序方式，我们可以通过相应的环境来判断使用使用哪种排序，使用希尔排序时要记得注意起始位置时0还是gap，从而来判断end的值为什么，为了之后的多种情况，所以我们要熟悉多种排序方法。
原文地址：https://blog.csdn.net/m0_73736626/article/details/142392898
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！