浙江省火电建设公司网站,广州开发网站设计,舒城县建设局官方网站,济南企业型网站文章目录插入排序概念插入排序分为2种一 .直接插入排序直接插入排序时间复杂度二.希尔排序希尔排序时间复杂度效率比较插入排序概念
直接插入排序是从一个有序的序列中选择一个合适的位置进行插入#xff0c;这个合适的位置取决于是要升序排序还是降序排序。
每一次进行排序…
文章目录插入排序概念插入排序分为2种一 .直接插入排序直接插入排序时间复杂度二.希尔排序希尔排序时间复杂度效率比较插入排序概念
直接插入排序是从一个有序的序列中选择一个合适的位置进行插入这个合适的位置取决于是要升序排序还是降序排序。
每一次进行排序之后这段数据都是有序的。 提示以下是本篇文章正文内容下面案例可供参考
插入排序分为2种
一 .直接插入排序
直接插入排序是从一段数据中将一个数据在合适的位置插入。
案例 一张图弄懂直接插入排序
代码如下
void InsertSort(int * a,int n )
{for(int i 0;in-1;i){int end i;//保存待插入元素int tmp a[end1];while(end0){if(a[end]tmp){//把end往后挪a[end1] a[end];//end再往前走 end--;}else{break;}}//由于不管是在中间的任意地方插入还是在end的末尾插入即tmp是最大的情况//都是在end后面的位置插入所以来到这里进行合并a[end1] tmp;}
}
直接插入排序时间复杂度
直接插入排序的时间复杂度为O(N^2)因为最坏的情况是逆序的情况
每一次插入需要挪动的次数为1234…n-2n-1 n*n/2
所以最坏情况下的时间复杂度为O(n^2)
二.希尔排序
希尔排序可以被认为是优化后的直接插入排序。
具体优化过程如下
给定一个gap这个gap是把待插入的数据分成gap组每组之间的间隔为gap长度 给定一个gap这个gap是把待插入的数据分成gap组每组之间的间隔为gap长度 给定一个gap这个gap是把待插入的数据分成gap组每组之间的间隔为gap长度
重要的事情说三遍。
比如 令gap 3即待插入的数据的间隔为3不同于直接插入排序直接插入排序是第一个和第二个数据的间隔永远为1而对于希尔排序当gap 3时第一个数据和第二个数据的间隔为3。 当我们把该组的元素两两比较时大的元素就会更快地往后走。 第二轮是将待插入元素8和9比较因为9后面的第一个元素不再是7而是9gap的位置处的数据即8 再将9和8进行比较将8插入到9位置处。
当然这是每组组内的比较
放眼整个希尔排序来说是多组同时进行的。
可以发现 当gap越大大的元素越快挪到后面 当gap越小小的元素越慢挪到后面 当gap 1时就相当于上面提到的直接插入排序。
回到上面的案例gap 3所以需要将数据分成3组每组的间隔为3个长度。 如上图此时每个元素都可以被覆盖到。 相当于同时把gap组中大的元素更快挪到后面
我们把上面的过程成为预排序
也就是说完成上面的操作之后整个数据并不是有序的而是 接近有序
比如上面的案例完成预排序后整组数据为 此时是接近有序所以此时令gap 1即最后接近有序的时候进行直接插入排序即可。
注意gap的取值是不确定的 gap取值越大大的数据越快挪到后面但越不接近有序 gap取值越小大的数据越慢挪到后面但越接近有序
总之gap是一定不能固定并且gap的取值最后必须为1。
gap的取值应该是从大逐渐到小过渡的。
gap的取值一般是
初始化gap n
进入轮回时
gap gap/31 或者 gap gap/2每次轮完一轮后gap都会减小。
当gap的取值是gap gap/2时时间复杂度为O(N*logN)logN是以2为底N的对数
最坏情况同样为逆序 最后一轮gap 1此时为直接插入排序则N/2/2/2/…/2 1 每次轮回一次gapgap都会/2最后一次gap 1则需要比较的次数是logN(以2为底N的对数)
希尔排序时间复杂度
总的时间复杂度为遍历整组元素的次数O(N)*每次遍历进行插入的次数O(logN) — O(N * logN)
同理当gap的变化是gap gap/3-1时 最坏情况下逆序每次轮回需要插入的次数是
(((N/31) /31)/31)… 1 对于时间复杂度可忽略掉1项所以每次轮回插入次数log3 (N) ,以3为底N的对数
总时间复杂度为O(N*log3 (N))
经过前人计算希尔排序平均时间复杂度为 O(N^1.3) 实现代码
void ShellSort(int* a, int n)
{//当gap越大大的值越快到达最后的位置,但越不接近有序//当gap越小大的值越慢到达最后的位置但越接近有序//当gap值越接近1排序越接近顺序//刚gap 1时就是直接插入排序int gap n;while (gap 1){//两种方式均可gap可以任取任何值但是都必须保证gap最后一定为1//gap gap / 2;gap gap / 3 1;//在这里就是把间隔多组的数据同时排列for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){//小于的情况需要挪动数据if (a[end] tmp){a[end gap] a[end];end - gap;}//大于或者等于的情况直接插入end后面else{break;}}//由于最终都需要插入end后面所以在循环之外插入a[end gap] tmp;}}
}
总结希尔排序是在直接插入排序的基础上引入一个gap这个gap把数据分成了gap组并且每组元素之间的间隔也为gap。 gap每次都会逐渐减小并且最后gap一定为1当gap为1时代表完成了预排序 最后一步进行直接插入排序。 效率比较
void TestOP()
{srand(time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);assert(a1 a2);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}//计算到这个走位置的时间msint begin1 clock();InsertSort(a1, N);int end1 clock();//末位置-初位置就是时间差int begin2 clock();ShellSort(a2, N);int end2 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);free(a1);free(a2);
}int main()
{TestOP();return 0;
}可以看到当排序数据为100w个时直接插入排序和希尔排序差距超过了2000倍。
直接插入排序和希尔排序的效率相比数据越多希尔排序较于直接插入排序的优化越大。
