希尔排序算法，C语言实例代码详解

2022-07-1717:18:36数据结构与算法Comments1,264 views字数 1072阅读模式
  1. 复杂度与稳定性

算法时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

最坏情况：O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

最好情况：O(n)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

平均情况：O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

稳定性：不稳定排序文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

2.过程介绍文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

希尔排序，又名递减增量排序算法，是一种非稳定的更高效的插入排序，在对几乎已经排好序的数据操作时，效率极高，即可以达到线性排序的效率，直接插入排序整体来说是低效的，因为插入排序每次只能将数据移动一位；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

过程如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

  1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
  2. 按增量序列个数 k，对序列进行 k 趟排序；
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
  1. 图示过程
第一趟1050302070704060
第二趟1020305040607070
第三趟1020304050607070
第四趟1020304050607070

可以见的，相比直接插入排序由于可以每趟进行分段操作，故整体效率体现较高。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

4. 相关的代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

2文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

3文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

4文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

5文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

6文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

7文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

8文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

9文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

10文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

11文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

12文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

13文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

14文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

15文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

16文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

17文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

18文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

19文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

20文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

21文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

22文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

23文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

24文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

#include<iostream>文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

using namespace std;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

void shellSort(int arr[], int n) {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    int i, j, gap;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    for (gap = n / 2; gap > 0; gap /= 2) {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

        for (i = 0; i < gap; i++) {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

            for (j = i + gap; j < n; j += gap) {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

                for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

                    swap(arr[k-gap], arr[k]);文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

                }文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

            }文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

        }文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    }文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

}文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

int main() {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    int a[8]= {70,50,30,20,10,70,40,60};文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    int n=8;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    shellSort(a,n);文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    for(int i=0; i<n; i++) {文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

        cout<<a[i]<<' ';文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    }文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

    return 0;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

}文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25226.html
  • 本站内容整理自互联网，仅提供信息存储空间服务，以方便学习之用。如对文章、图片、字体等版权有疑问，请在下方留言，管理员看到后，将第一时间进行处理。
  • 转载请务必保留本文链接：https://www.cainiaoxueyuan.com/suanfa/25226.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定