单次插排:
那么,对于一个数组,可以从a[0]开始,直至a[sz-1],进行插入排序。
注意:end的值最大为sz-1-1,超过会越界。
时间复杂度:O(N^2),逆序的情况。
但最好的情况为O(N),相比之下,优于冒泡排序。
当序列越趋向于有序,该排序就越好。
void InsertSort(int* a, int sz)
{
assert(a);
for (int i = 0; i < sz - 1; i++)
{
//[0,end]有序,再插入后一个值还保持有序
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;
}
}
希尔排序
希尔排序是直接插入排序的小变形。
先进行预排序,使数列接近于有序,再进行直接插入排序。
代码实现:
注:gap和sz有直接关系
//排升序,gap越大,大的数更快到后面,小的更快到前面,但越不接近有序
//排升序,gap越小,越接近有序;gap=1时,就是直接插入排序
void ShellSort(int* a, int sz)
{
int gap = sz;
while (gap > 1)
{
//分组
gap = gap / 3 + 1;//保证最后一次一定 =1
for (int i = 0; i < sz - 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;
}
}
}



