云南网站建设选天软,wordpress插件的语言设定,wordpress改写rewrite,实时热点新闻及评论1.插入排序的时间复杂度#xff1a;最坏为从1到n的等差数列之和。也就是n的平方#xff0c;但最好为n
2.希尔排序的思路#xff1a; 1.预排序#xff08;接近有序#xff09;#xff1a; 假设gap为一组#xff0c;总计gap组#xff0c;对gap组分别插入排序 2.插入排序…
1.插入排序的时间复杂度最坏为从1到n的等差数列之和。也就是n的平方但最好为n
2.希尔排序的思路 1.预排序接近有序 假设gap为一组总计gap组对gap组分别插入排序 2.插入排序
3.两种循环思路实现第一步预处理即将所有数据分成gap组gap越大大的数越快到后面小的数越快到前面gap越小挪动越慢越接近有序gap越大和越小时解决o(n)gap1时是直接插入排序并在组内完成插入排序
代码实现注释部分为另一种循环思路
void shellsort(int* a, int n)
{int gap3;//for (int j 0; j gap; j)//{//// for (int i j; i n - gap; i i gap)for(int i0;in-gap;i){int end n;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end end - gap;}else{break;}}a[end gap] tmp;//第一个位置}//}} 以上即为分组插入的思路而gap的核心写法为
void shellsort(int* a, int n)
{int gapn;
while(gap1)//for (int j 0; j gap; j)//{////
{
gapgap/31;
for (int i j; i n - gap; i i gap)for(int i0;in-gap;i){int end n;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end end - gap;}else{break;}}a[end gap] tmp;//第一个位置}//}}}
效果为不断趋近于有序,时复为gap*(12......n/gap),约为log3n到log2n之间
