- 插入排序
- 希尔排序
时间复杂度O(N*N)插入排序是稳定的
类似于摸牌的时候,一张一张摸,然后一张一张排序。
先来看一趟排序怎么排
首先把要排的数(x)存起来,然后跟前面排好的数组依次比较,遇到比x大的就覆盖掉x,再比较,直到遇到比x小的,或者循环结束,就停下来,把x的值再拿出来放到停下来的位置,算作一趟。
接下来就是怎么控制多次排序。
从头到尾遍历一遍即可
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int x = a[end + 1];
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = x;
}
}
希尔排序
时间复杂度O(N*logN) 希尔排序是不稳定算法
是插入排序的大优化,希尔排序是将待排序的数组元素 按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;
//效率稍微高一点点
//gap /= 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}



