青岛黄岛网站建设公司电话,搜房网,泰安肥城网站建设,WordPress百度收录代码1、简述#xff1a;
希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”#xff08;Diminishing Increment Sort#xff09;#xff0c;是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排…1、简述
希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”Diminishing Increment Sort是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。 [1]
2、复杂度
时间复杂度O(nlogn)~O(n²) (取决于增量的序列)
空间复杂度O(1) 3、稳定性不稳定的
由于多次插入排序我们知道一次插入排序是稳定的不会改变相同元素的相对顺序但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以shell排序是不稳定的。
4、例子
推导过程格努增量进行分组增量 序列长度/2; #include iostream
using namespace std;int main() {int arr[8] {45, 98, 66, 90, 88, 78, 25, 45};int len sizeof(arr)/sizeof(arr[0]);int gap len / 2;int count 0; // 记录输出次数用的可删除while (gap 1) {coutcount轮排序endl;// 将每个元素进行for (int i gap; i len; i) {// 对同个分组内的元素进行比较for (int j i - gap; j 0; j - gap) {if (arr[j] arr[j gap]) break;// 换位:方法一(交换两个数据不使用第三个变量)arr[j] arr[j] arr[j gap] - (arr[j gap] arr[j]);// 换位方法二(第三个变量)
// int tmp arr[j gap];
// arr[j gap] arr[j];
// arr[j] tmp;}}// 缩小增量gap gap / 2;for (int a 0;a len;a) {cout arr[a] ;}coutendl;}cout最后结果;for (int i 0;i len;i) {cout arr[i] ;}return 0;
}
输出结果
1轮排序
45 78 25 45 88 98 66 90
2轮排序
25 45 45 78 66 90 88 98
3轮排序
25 45 45 66 78 88 90 98
最后结果25 45 45 66 78 88 90 98 参考
千锋教育-希尔排序希尔排序为什么会那么牛那么快能够证明吗 - 知乎
百度百科-希尔排序百度百科-验证 生命不息学习不止若有不正确的地方欢迎指正。
