背景

3つの簡単なソートアルゴリズム(バブル、選択、挿入)でソートを挿入するアルゴリズムが一番いいですが、挿入過程では大量の移動が必要になる可能性がありますが、要素をできるだけ少なくするにはどうすればいいですか?ヒルソートはこの問題に対する考え方に基づいて考えられたものであり,ヒルソートがソートされた配列のソート効率に特に優れている(O(nに近い)ことを考慮すると,ヒルソートはまず大きな間隔で間隔の要素を挿入ソートし,間隔を1にするまで縮小して上述の過程を繰り返す.

インプリメンテーション

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace DataStuctureStudy.Sorts
 8 {
 9     class ShellSort
10     {
11         public static void Sort(int[] items)
12         {
13             var h = 1;
14             while (h <= (items.Length - 1) / 3)
15             {
16                 h = 3 * h + 1;
17             }
18 
19             //      h        ， ：（0，h，2h）、（1，h + 1，2h + 1）。
20             while (h >= 1)
21             {
22                 //   outer               （    h）        。
23                 // h            。
24                 for (var outer = h; outer < items.Length; outer++)
25                 {
26                     var temp = items[outer];
27                     var inner = outer;
28                     while (inner >= h && items[inner - h] > temp) //        ：     while。
29                     {
30                         items[inner] = items[inner - h];
31                         inner = inner - h;
32                     }
33                     items[inner] = temp;
34                 }
35                 h = (h - 1) / 3;
36             }
37         }
38     }
39 }

コメント

間隔の選択は重要な要素であり、ここではよく使われるアルゴリズムを選択しました.