背景
在三种简单的排序算法中(冒泡、选择和插入)插入排序的算法最好,不过插入过程可能需要进行大量的移动,如何尽可能少的移动元素呢?希尔排序正是基于对这个问题的思考而想出来的,考虑到希尔排序对已排序数组的排序效率尤为好(接近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 ShellSort10 {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 }
备注
间隔的选择是一个关键因素,这里我选择了一个大家经常使用的算法。