更新两个的排序:直接插入排序和希尔排序,两者的关联是很大的,所以放一起来说。
直接插入排序直接插入排序:假设前n-1个数是有序的,将第n个数与前面的数进行比较,将它插入到合适的位置,通俗来讲,就是将一个数插入到已有的有序队列当中进行比较,然后按照规则把这个数插入到合适的位置。
比如有一堆数 1 2 3 5 9 现在想插入4,原数列是有序且升序,那么插入4就是从9开始比较,4比9小,9就需要向后挪一个位置,再与5比,4比5小,5也需要向后挪一个位置,再与3比,4比3大,4就插入5挪出来的位置,一次插入排序就完成了。
下面动图演示一个乱序的插入排序:
代码:
//插入排序
// 2 1 4 3 6
//时间复杂度:O(N^2) 逆序
//最好:O(N) 接近顺序有序
void InsertSort(int*a,int n)
{
for(int i=0;i=0)
{
if(temp=0时继续比较
}
else
{
break;
}
}
//循环结束有两种情况:1、end减为-1 放在end的后面一个位置
//2、temp>a[end] 放在end的后一个位置
a[end+1]=temp;
}
}
直接插入排序的时间复杂度是O(N^2)
希尔排序希尔排序:其实就是对直接插入排序的优化,希尔排序有两个阶段,第一个阶段是预排序,第二个阶段是对预排序排好的顺序再进行直接插入排序。
具体来说:希尔排序是基于插入排序的以下两点性质而提出改进方法的:
1.插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
2.插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;
希尔排序的基本思想是:
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,
待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。
希尔排序实际上是直接插入排序的优化版本。
void ShellSort(int* a,int n)
{
//gap>1 预排序--接近有序
//gap==1 直接插入排序
int gap = n;
while(gap>1)//while循环的时间复杂度:log以3为底N的对数
{
gap=gap/3+1;//最后一次一定是1
//gap = gap/2;//预排会多一些
//间隔为gap的多组并排
for(int i=0;i=0)
{
if(temp



