插入排序
基本思想
插入排序的基本思想就是在一串顺序的排序后面插入数据,然后按照顺序进行排序。
扑克牌就是典型的插入排序
代码实现
void Swap(int* a, int* b)
{
int tmp = 0;
tmp = *a;
*a = *b;
*b = tmp;
}
//n为数组的个数
void InSertSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp > a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void print(int* a,int n)
{
for (int i = 0;i < n;++i)
{
printf("%d ", a[i]);
}
}
结果如下:
希尔排序
基本思想
希尔排序分为预排序和插入排序两部分。
预排序
什么是预排序呢?
就是按照给定的一个数gap,按照间隔gap把数据分为几组,在组内进行插入排序。
示意图如下:
按照间隔为2分为3组
第一组:4 1 8 2
第二组:5 6 10
第三组:3 6 9
然后第一组进行插入排序,然后第二组进行插入排序,第三组进行插入排序。
最后排序结果是这个:
这个就是预排序,进行完预排序后,在进行插入排序就可以了。
预排序代码实现
这是一组的
for (int i = 0; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
然后我们套一层循环,就是三组的
for (int j = 0; j < gap; ++j)
{
for (int i = j; i < n-gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
希尔排序
代码如下:
void ShellSort(int* a, int n)
{
int gap = n;
// gap > 1时是预排序,目的让他接近有序
// gap == 1是直接插入排序,目的是让他有序
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
这个代码和上面的预处理加上直接插入不太一样,想想看为啥不一样。