C#希尔排序

1.概要

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，他是简单插入排序经过改进之后的一个更高效的版本，也成为缩小增量排序。.

希尔排序算法基本思想

希尔排序是吧记录按下标的一定增量分组，对每组使用直接插入排序算法排序：随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

2.详细内容

public class ShellSort
  {
       public static void Sort(int[] arr)
      {
           int gap = arr.Length / 2;
           while (gap > 0)
          {
               for (int i = gap; i < arr.Length; i++)
              {
                   int insertVal = arr[i];
                   int insertIndex = i - gap;
                   while (insertIndex >= 0 && insertVal < arr[insertIndex])
                  {
                       arr[insertIndex + gap] = arr[insertIndex];
                       insertIndex -= gap;
                  }
                   arr[insertIndex + gap] = insertVal;
              }
               gap /= 2;
          }
           Console.WriteLine(string.Join(' ', arr));
      }
  }

   internal class Program
  {
       static void Main(string[] args)
      {
           int[] array = { 8,9,1,7,2,3,5,4,6,0};
           ShellSort.Sort(array);
           Console.Read();
      }
  }