希尔排序（shell Sort）

  • 平均时间复杂度：O(nlogn)
  • 最好情况：O(nlogn)
  • 最坏情况：O(nlogn)
  • 空间复杂度：O(1)
  • 排序方式：内部
  • 稳定性：稳定

    C++代码实现

    1. void shellSort(vector<int>& arr) {
    2.   int len = arr.size();
    3.   int gap = 1;    //增量间隔
    4.   while (gap < len / 3) {
    5.       gap = 3 * gap + 1;
    6.   }
    7.   while (gap >= 1) {
    8.       //此处是插入排序的改进(根据gap间隔进行插入排序)
    9.       for (int i = gap; i < len; i++) {
    10.           for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
    11.               swap(arr[j], arr[j - gap]);
    12.           }
    13.       }
    14.       gap = gap / 3;
    15.   }
    16. }

1. 算法步骤

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

    优化步骤

    ① 希尔排序是插入排序的改进，所以可以使用插入排序的优化

    2. 动图演示

shell.gif