徐州做网站需要多少钱,河南做外贸网站的公司,广州建站外贸网站,广州古柏广告策划有限公司希尔排序虽然是直接插入排序的升级版本#xff0c;和插入排序有着相同的特性#xff0c;即原始数组有序度越高则算法的时间复杂度越低#xff08;预排序机制#xff09;#xff0c;但是是不稳定排序算法。
为了降低算法的时间复杂度#xff0c;所以我们需要在排序之前尽…希尔排序虽然是直接插入排序的升级版本和插入排序有着相同的特性即原始数组有序度越高则算法的时间复杂度越低预排序机制但是是不稳定排序算法。
为了降低算法的时间复杂度所以我们需要在排序之前尽可能提高数组的有序度。
希尔排序定义一个间隔变量gap对待排序数组进行分组将下标间隔为gap的多个数组分为一组每次遍历都只对组内数据进行排序然后降低gap重复上述分组排序最后gap1便是进行直接插入排序但此时待排序数组的有序度已经很高了故最后一次排序的时间复杂度接近于。 gap的取值可以自定义通常会使用进行取值。
希尔排序的时间复杂度难以精确统计与gap的取值算法和原始数组的有序性强相关而我们算法经大量实验研究得希尔排序的时间复杂度为~。
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1;int i gap;for (; i n; i) {int j i;int end arr[j];while (j gap arr[j - gap] end){arr[j] arr[j - gap];j - gap;}arr[j] end;}}
}
