直接插入排序待整个序列中的记录基本有序时对全体记录进行直接插入排序。

1.减少待排序记录

的元素组成一组可以分为2组。

按照直接插入排序的方法对每个组进行排序。

第三趟排序

这样相隔距离为1的元素组成一组即只有一组。

按照直接插入排序的方法对每个组进行排序。

此时排序已经结束。

注需要注意一下的是图中有两个相等数值的元素5和5。

我们可以清楚的看到在排序过程中两个元素位置交换了。

代码实现

1.希尔排序的效率取决于增量值gap的选取时间复杂度并不是一个定值。

2.开始时gap取值较大子序列中的元素较少排序速度快克服了直接插入排序的缺点其次gap值逐渐变小后虽然子序列的元素逐渐变多但大多元素已基本有序所以继承了直接插入排序的优点能以近线性的速度排好序。

4.希尔排序并不只是相邻元素的比较有许多跳跃式的比较难免会出现相同元素之间的相对位置发生变化。

比如上面的例子中希尔排序中相等数据5就交换了位置所以希尔排序是不稳定的算法。

起泡排序冒泡排序

两两比较相邻记录的关键码如果反序则交换直到没有反序的记录为止。

templateclass

首先选择一个轴值即比较的基准通过一趟排序将待排序记录分割成独立的两部分前一部分记录的关键码均小于或等于轴值后一部分的关键码均大于或等于轴值然后分别对这两部分重复上述方法直到整个序列有序。

比较序列中第一个记录、最后一个记录和中间记录的关键码取关键码居中的作为轴值并调换到第一个记录的位置

随机选取轴值

i,index;for(i1;in;i){indexi;for(ji1;jn;j)if(r[j]r[index])

indexj;if(index!i)

堆是具有一下性质的完全二叉树每个结点的值都小或者等于其左右孩子结点的值称为小根堆或者每个结点的值都大于或等于其左右孩子结点的值称为大根堆

·较小结点靠近根结点但不绝对

首先将待排序的记录序列构造成一个堆此时选出了堆中所有记录的最小者然后将它从堆中移走并将剩余的记录再次调整成堆这样又找出了次小记录。

以此类推直到堆中只有一个记录。

动图演示https://vdn6.vzuu.com/SD/3bb38dfe-236a-11eb-8039-a6caf32b14c9.mp4?pkeyAAUyrCY8VNkvMdMU1V6cmk2JYP4PY3XxcITCzTRSwUQMzfJJEGolTKO0ORqU97S6zQFMp3fpKyqia3U_GdbZhZe1cavc.0.0fmp4pu078babd7bu078babd7expiration1704189211vks6https://vdn6.vzuu.com/SD/3bb38dfe-236a-11eb-8039-a6caf32b14c9.mp4?pkeyAAUyrCY8VNkvMdMU1V6cmk2JYP4PY3XxcITCzTRSwUQMzfJJEGolTKO0ORqU97S6zQFMp3fpKyqia3U_GdbZhZe1cavc.0.0fmp4pu078babd7bu078babd7expiration1704189211vks6

void

{ik;j2*i;tempr[i];//将筛选记录暂存while(jm)

r[j]r[j1])

{for(in/2;i1;i--)//初建堆sift(r,i,n);for(i1;in;i){r[1]r[n-1i];//移走堆顶sift(r,1,n-i);//重建堆}

时间复杂度O(nlog2n)