dart實現(xiàn)希爾排序(Shell sort)

希爾排序(Shell sort)

[toc]

1959年由唐納德·希爾（Donald Shell）提出

1.思路

  • 希爾排序把序列看作是一個矩陣，分成 ?? 列，逐列進行排序
    • ?? 從某個整數(shù)逐漸減為1
    • 當 ?? 為1時，整個序列將完全有序
  • 因此，希爾排序也被稱為遞減增量排序（Diminishing Increment Sort）

矩陣的列數(shù)取決于步長序列（step sequence）

  • 比如，如果步長序列為{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列進行排序
  • 不同的步長序列，執(zhí)行效率也不同

1.1舉例

希爾本人給出的步長序列是 ??/2^??，比如 ?? 為16時，步長序列是{1, 2, 4, 8}
例如
原數(shù)組為
a1 = [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]

  1. 第一次分為8列，則分成2個數(shù)組
    [16,15,14,13,12,11,10,9]
    [ 8, 7, 6, 5, 4, 3, 2,1]
    逐列進行比較數(shù)組變成
    [ 8, 7, 6, 5, 4, 3, 2,1]
    [16,15,14,13,12,11,10,9]
    然后合并成一個數(shù)組
    a2=[ 8, 7, 6, 5, 4, 3, 2,1,16,15,14,13,12,11,10,9]
  2. 再將數(shù)組a2分為4列，則分為4個數(shù)組
    [ 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]
    然后合并成一個數(shù)組
    a3=[ 4, 3, 2, 1, 8, 7, 6, 5,12,11,10, 9,16,15,14,13]
  3. 再將數(shù)組a3分為2列，則分成的那個8個數(shù)組
    [ 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]
    然后合并成一個數(shù)組
    a4=[ 2, 1, 4, 3, 6, 5, 8, 7,10, 9,12,11,14,13,16,15]
  4. 在將數(shù)組a4分為1列，則分成16個數(shù)組，
    [ 2]
    [ 1]
    [ 4]
    ……
    [16]
    [15]
    逐列進行比較,然后合并成一個數(shù)組
    a5=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]完成

每次進行拆分列數(shù)后，逆數(shù)對的個數(shù)減少
因此希爾排序底層一般使用插入排序對每一列進行排序，也很多資料認為希爾排序是插入排序的改進版

1.2代碼思路

1.2.1 編寫函數(shù)返回步長序列

這里給希爾給的步長序列希爾本人給出的步長序列是 ??/2^??，比如 ?? 為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 編寫函數(shù)對第col列進行插入排序

  • 假設元素在第 col 列、第 row 行，步長（總列數(shù)）是 step
  • 那么這個元素在數(shù)組中的索引是 col + row * step
  • 所以插入排序for循環(huán)中每次增加的數(shù)字為step，而不再是1
  • 因此原來插入排序相應的加1減1的操作都變成了 加step減step

  ///
  /// Author: liyanjun
  /// description: 分成step列進行排序
  _sout(int step) {
    //col 代表列，從
    for (var col = 0; col < step; col++) {
      //第col列進行排序 進行插入排序 這里的代碼是插入排序的移動代碼的優(yōu)化版本
      // 原來相應的加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列進行排序 進行插入排序 這里的代碼是插入排序的移動代碼的優(yōu)化版本
      // 原來相應的加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個數(shù)，最小是1，最大是20000
  List<int> list = IntergerTools.random(10, 1, 20); //生成10000個數(shù)，最小是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)，屬于不穩(wěn)定排序
最好情況是步長序列只有1，且序列幾乎有序，時間復雜度為 O(n)
希爾給出的步長序列 ??/2^??，的最壞情況時間復雜度是 O(n^2)

目前已知的最好的步長序列，最壞情況時間復雜度是 O(n^{4/3}) ，1986年由Robert Sedgewick提出
步長算法思路：

  1. 如果k是偶數(shù)，則步長序列為9*(2^k-2^{k/2})+1
  2. 如果k是奇數(shù)，則步長序列為8*2^k-6*2^{(k+1)/2}+1 

  ///
  /// Author: liyanjun
  /// description: 科學家發(fā)現(xiàn)最快的步長序列 ，最壞情況時間復雜度是 $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;
  }
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容