希尔排序(Shell sort)

[toc]

1959年由唐纳德·希尔（Donald Shell）提出

1.思路

• 希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序
  • 𝑚 从某个整数逐渐减为1
  • 当 𝑚 为1时，整个序列将完全有序
• 因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）

矩阵的列数取决于步长序列（step sequence）

• 比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序
• 不同的步长序列，执行效率也不同

1.1举例

希尔本人给出的步长序列是 ，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}
例如
原数组为
a1 = [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]

1. 第一次分为8列，则分成2个数组
   [16,15,14,13,12,11,10,9]
   [ 8, 7, 6, 5, 4, 3, 2,1]
   逐列进行比较数组变成
   [ 8, 7, 6, 5, 4, 3, 2,1]
   [16,15,14,13,12,11,10,9]
   然后合并成一个数组
   a2=[ 8, 7, 6, 5, 4, 3, 2,1,16,15,14,13,12,11,10,9]
2. 再将数组a2分为4列，则分为4个数组
   [ 8, 7, 6, 5]
   [ 4, 3, 2, 1]
   [16,15,14,13]
   [12,11,10, 9]
   逐列进行比较
   [ 4, 3, 2, 1]
   [ 8, 7, 6, 5]
   [12,11,10, 9]
   [16,15,14,13]
   然后合并成一个数组
   a3=[ 4, 3, 2, 1, 8, 7, 6, 5,12,11,10, 9,16,15,14,13]
3. 再将数组a3分为2列，则分成的那个8个数组
   [ 4, 3]
   [ 2, 1]
   [ 8, 7]
   [ 6, 5]
   [12,11]
   [10, 9]
   [16,15]
   [14,13]
   逐列进行比较
   [ 2, 1]
   [ 4, 3]
   [ 6, 5]
   [ 8, 7]
   [10, 9]
   [12,11]
   [14,13]
   [16,15]
   然后合并成一个数组
   a4=[ 2, 1, 4, 3, 6, 5, 8, 7,10, 9,12,11,14,13,16,15]
4. 在将数组a4分为1列，则分成16个数组，
   [ 2]
   [ 1]
   [ 4]
   ……
   [16]
   [15]
   逐列进行比较,然后合并成一个数组
   a5=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]完成

每次进行拆分列数后，逆数对的个数减少
因此希尔排序底层一般使用插入排序对每一列进行排序，也很多资料认为希尔排序是插入排序的改进版

1.2代码思路

1.2.1 编写函数返回步长序列

这里给希尔给的步长序列希尔本人给出的步长序列是 ，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}

  ///
  /// Author: liyanjun
  /// description:
  ///采用希尔给出的步长序列
  List<int> _createShellStepSequence() {
    List<int> stepSequence = [];
    int step = list.length;
    if (step == 0) return [];
    if (step == 1) return [1];
    while (step > 1) {
       step >>= 1;
      stepSequence.add(step);
    }
    return stepSequence;
  }

1.2.2 编写函数对第col列进行插入排序

• 假设元素在第 col 列、第 row 行，步长（总列数）是 step
• 那么这个元素在数组中的索引是 col + row * step
• 所以插入排序for循环中每次增加的数字为step，而不再是1
• 因此原来插入排序相应的加1减1的操作都变成了 加step减step

  ///
  /// Author: liyanjun
  /// description: 分成step列进行排序
  _sout(int step) {
    //col 代表列，从
    for (var col = 0; col < step; col++) {
      //第col列进行排序 进行插入排序 这里的代码是插入排序的移动代码的优化版本
      // 原来相应的加1减1的操作都变成了 加step减step
      for (var begin = col+step; begin < list.length; begin +=step) {
        int cur = begin;
        T v = list[cur];
        while (cur > col && cmpElement(v, list[cur - step]) < 0) {
          list[cur] = list[cur - step];
          cur -= step;
        }
        list[cur] = v;
      }
    }
  }

1.2.3 遍历步长序列

 sort() {
    List<int> stepSequence = _createShellStepSequence();
    for (var step in stepSequence) {
      _sout(step);
    }
  }

2.代码

/// Date: 2020-11-09 00:01:18
/// FilePath: /algorithm/sort/shell_sort.dart
/// Description: 希尔排序
///

class ShellSort<T extends Comparable<T>> extends Sort<T> {
  @override
  sort() {
    List<int> stepSequence = _createShellStepSequence();
    for (var step in stepSequence) {
      _sout(step);
    }
  }

  ///
  /// Author: liyanjun
  /// description: 分成step列进行排序
  _sout(int step) {
    //col 代表列，从
    for (var col = 0; col < step; col++) {
      //第col列进行排序 进行插入排序 这里的代码是插入排序的移动代码的优化版本
      // 原来相应的加1减1的操作都变成了 加step减step
      for (var begin = col+step; begin < list.length; begin +=step) {
        int cur = begin;
        T v = list[cur];
        while (cur > col && cmpElement(v, list[cur - step]) < 0) {
          list[cur] = list[cur - step];
          cur -= step;
        }
        list[cur] = v;
      }
    }
  }

  ///
  /// Author: liyanjun
  /// description:
  ///采用希尔给出的步长序列
  List<int> _createShellStepSequence() {
    List<int> stepSequence = [];
    int step = list.length;
    if (step == 0) return [];
    if (step == 1) return [1];
    while (step > 1) {
      step >>= 1;
      stepSequence.add(step);
    }
    return stepSequence;
  }

验证

main(List<String> args) {
  // List<int> list = IntergerTools.random(10000, 1, 20000); //生成10000个数，最小是1，最大是20000
  List<int> list = IntergerTools.random(10, 1, 20); //生成10000个数，最小是1，最大是20000
  List<Sort> sortList = [
    // HeapSort<num>(),
    // SelectSort<num>(),
    // BubbleSort2<num>(),
    // BubbleSort1<num>(),
    // BubbleSort<num>(),
    // InsertSort<num>(),
    // InsertSort1<num>(),
    // InsertSort2<num>(),
    // MergeSort<num>(),
    // QuickSort<num>(),
    ShellSort<num>(),
  ];
  testSorts(list, sortList);
}

void testSorts(List<int> list, List<Sort> sorts) {
  print('排序前 ：$list');
  for (Sort sort in sorts) {
    List<int> newList = List.from(list);
    sort.setList(newList);
    sort.sortPrint();
    Asserts.test(IntergerTools.isAscOrder(sort.list));
     print('排序后 ：${sort.list}');
  }
  sorts.sort(); //比较
  for (Sort sort in sorts) {
    print(sort);
  }
}

结果

排序前 ：[2, 18, 8, 20, 10, 9, 10, 12, 7, 9]
排序后 ：[2, 7, 8, 9, 9, 10, 10, 12, 18, 20]
【ShellSort<num>】
耗时：0.002s (2ms)     比较：27    交换：0
-----------------

3.时间复杂度

空间复杂度为O(1)，属于不稳定排序
最好情况是步长序列只有1，且序列几乎有序，时间复杂度为 O(n)
希尔给出的步长序列 ，的最坏情况时间复杂度是

目前已知的最好的步长序列，最坏情况时间复杂度是 ，1986年由Robert Sedgewick提出
步长算法思路：

1. 如果k是偶数，则步长序列为
2. 如果k是奇数，则步长序列为

  ///
  /// Author: liyanjun
  /// description: 科学家发现最快的步长序列 ，最坏情况时间复杂度是 $O(n^{4/3})$
  ///
  List<int> _sedgewickStepSequence() {
    List<int> stepSequence = [];
    int k = 0, step = 0;
    while (true) {
      if (k % 2 == 0) {
        int powResult = pow(2, k >> 1); //求2^{k/2}的结果
        step = 1 + 9 * (powResult * powResult - powResult);
      } else {
        int pow1 = pow(2, (k - 1) >> 1); //求2^{k-1/2}的结果
        int pow2 = pow(2, (k + 1) >> 1); //求2^{k-1/2}的结果
        step = 1 + 8 * pow1 * pow2 - 6 * pow2;
      }
      if (step >= list.length) break;
      stepSequence.insert(0, step);
      k++;
    }
    return stepSequence;
  }