希尔排序：
插入排序的升级版，主要采用了分组的策略，采用逐渐减小步长来控制分组的大小，各组内采用插入排序，当步长减小为1的时候，大部分数据都已经有序，所以较插入排序优化了许多。
代码：
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; using System.Net; using System.Threading;namespace ConsoleApplication1 {class Program{static void Main(string[] args){for (int i = 1; i <= 5; i++){List<int> list = new List<int>();//插入2k个随机数到数组中for (int j = 0; j < 20000; j++){Thread.Sleep(1);list.Add(new Random((int)DateTime.Now.Ticks).Next(10000, 1000000));}Console.WriteLine("\n第" + i + "次比较：");Stopwatch watch = new Stopwatch();watch.Start();var result = ShellSort(list);//这里这个single=>single不懂 watch.Stop();Console.WriteLine("\n希尔排序耗费时间：" + watch.ElapsedMilliseconds);Console.WriteLine("输出前是十个数："+string.Join(",",result.Take(10).ToList()));watch.Start();result = InsertSort(list);watch.Stop();Console.WriteLine("\n插入排序耗费时间：" + watch.ElapsedMilliseconds);Console.WriteLine("输出前是十个数：" + string.Join(",", result.Take(10).ToList()));}Console.ReadLine();}static List<int> ShellSort(List<int> list){int step = list.Count / 2;while (step >= 1){for (int i = step; i < list.Count; i++){int temp = list[i];int j;for (j = i - step; j >= 0 && temp < list[j]; j = j - step){list[j + step] = list[j];}list[j + step] = temp;}step = step / 2;}return list;}//插入排序算法static List<int> InsertSort(List<int> list){for (int i = 1; i < list.Count; i++){int temp = list[i];int j;for (j = i - 1; j >= 0 && temp < list[j]; j--){list[j + 1] = list[j];}list[j + 1] = temp;}return list;}} }
不过这里有个问题，我的希尔排序并不比插入排序快多少，不知道问题出在哪里。。。。。待解决
