coderbruis
diff --git a/‎notes/algorithms/希尔排序算法.md‎
Lines changed: 46 additions & 0 deletions b/‎notes/algorithms/希尔排序算法.md‎
Lines changed: 46 additions & 0 deletions
diff --git a/‎notes/pictures/shellSort.gif‎
271 KB b/‎notes/pictures/shellSort.gif‎
271 KB
@@ -0,0 +1,46 @@
+## 前言
+
+希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
+
+希尔排序是基于插入排序的以下两点性质而提出改进方法的：
+
+- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
+- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
+
+希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
+
+动态图：
+
+![希尔排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/shellSort.gif)
+
+
+## 正文
+
+### 代码实现
+
+```
+public class ShellSort {
+    public static void sort(int[] arr) {
+        int n = arr.length;
+
+        int h = 1;
+
+        while (h < n / 3) {
+            h = 3 * h + 1;
+        }
+
+        while (h >= 1) {
+            for (int i = h; i < n; i++) {
+                int e = arr[i];
+                int j = i;
+                for (; j >= h && e < arr[j-h]; j -= h) {
+                    arr[j] = arr[j-h];
+                }
+                arr[j] = e;
+            }
+
+            h /= 3;
+        }
+    }
+}
+```