数据结构:插入排序,希尔排序(缩小增量排序)

1.直接插入排序

当插入第 i 个元素时,前面的数据已经排好序了,将后续的数据按大小插入到前面已经排好序的数组中,就是插入排序

特点

1.元素集合越接近有序,时间效率越高

2.时间复杂度O(N^2)

3.空间复杂度O(1)

//插入排序
void InsertSort(int* a, int length)
{
for (int i = 0; i < length - 1; i++)
{
int end = i;//已经排好的数组的尾部
int temp = a[end + 1];
while (end >= 0)
{
if (temp < a[end])//小就向前移
{
a[end + 1] = a[end];
--end;
}
else
{

break;
}
}
a[end + 1] = temp;
}
}

2.希尔排序

时间复杂度约为O(N ^ 1.3)

先进行预排序 -- 目标 : 接近有序

然后再进行插入排序 -- 目标 : 有序

预排序

设定间距(两个数的下标之差)为gap,将彼此间距为gap的数进行插入排序

gap越大,数据跳的越快,大的数据更快到前面的位置,但是越不有序

gap越小,越接近有序

gap = 1时,就是插入排序

eg.

进行希尔排序时可以进行多次预排序,每次gap / 2,并且要求gap > 1保证最后一次预排序gap = 1,即完成排序

void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;//进行多次预排序,gap > 1保证最后一次预排序gap = 1,即完成排序
for (int j = 0; j < gap; ++j)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;//已经排好的数组的尾部
int temp = a[end + gap];
while (end >= 0)
{
if (temp < a[end])//小就向前移
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}
}

gap也可以取3,但是为了保证最后一次预排序时gap为1,还需要gap + 1

即

void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 3 + 1;//进行多次预排序,gap > 1保证最后一次预排序gap = 1,即完成排序
for (int j = 0; j < gap; ++j)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;//已经排好的数组的尾部
int temp = a[end + gap];
while (end >= 0)
{
if (temp < a[end])//小就向前移
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}
}

原文地址：https://blog.csdn.net/2301_80006788/article/details/136973806

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！