网站联盟接口怎么做,乐清网站推广公司,湖南 中小企业 网站建设,社交电商目录 前言#xff1a;
插入排序#xff1a;
希尔排序#xff1a; 前言#xff1a; 排序在我们生活中无处不在#xff0c;比如学生成就排名#xff0c;商品价格排名等等#xff0c;所以排序在数据结构的学习中尤为重要#xff0c;今天就为大家介绍两个经典的排序算法
插入排序
希尔排序 前言 排序在我们生活中无处不在比如学生成就排名商品价格排名等等所以排序在数据结构的学习中尤为重要今天就为大家介绍两个经典的排序算法插入排序和希尔排序。
插入排序
思路图 思路
从第二个元素开始和前面的元素依次比较如果前面的元素比它大则将该元素移到后一位如果该元素比它小则直接插入该元素后面。
代码实现
void InsertSort(int* a, int n)
{int i 0;for (i 0;i n-1;i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 时间复杂度 最坏情况下为O(N*N)此时待排序列为逆序或者说接近逆序 最好情况下为O(N)此时待排序列为升序或者说接近升序。 空间复杂度O(1) 希尔排序 其实希尔排序就是插入排序的进阶版可以说是希尔对插入排序进行了优化。
思路图 思路
步骤一预排序使数组接近有序
步骤二插入排序
先将每间隔gap个元素的数据分为一组将每组分别进行插入排序使其接近有序
gap逐渐减小gap减为1时就是进行步骤二的插入排序。
代码实现
void ShellSort(int* a, int n)
{int gap n;while(gap1){gap gap / 2;int i 0;for (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;}else{break;}}a[end gap] tmp;}}
}
纸上得来终觉浅绝知此事要躬行。快去实践一下吧。
