插入排序：希尔排序（不稳定）
【算法改进要点 】 直接插入排序法，在待排序的关键字序列基本有序且关键字个数 n 较少
时，其算法的性能最佳。 希尔排序又称缩小增量排序法，是一种基于插入思想的排序方法，
它利用了直接插入排序的最佳性质，①将待排序的关键字序列分成若干个较小的子序列，对
子序列进行直接插入排序，使整个待排序序列排好序。在时间耗费上，较直接插入排序法的
性能有较大的改进。②在进行直接插入排序时，若待排序记录序列已经有序时，直接插入排
序的时间复杂度可以提高到 O(n)。若待排序记录序列基本有序时，即序列中具有下列特性的
记录较少时： r[i].key<Max{ r[j].key}，（1≤j<i），直接插入排序的效率会大大提高。希尔排序
正是基于以上两点对直接插入排序进行了改进。
【 算法思想 】 先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。
①首先选定记录间的距离为 d i (i=1)，在整个待排序记录序列中将所有间隔为 d 1 的记录分成一组，进行组内直接插入排序；②然后取 i=i+1, 记录间的距离为 d i （d i <d i-1 ），在整个待排序记录序列中，将所有间隔为di 的记录分成一组，进行组内直接插入排序；
重复步骤②多次，直至记录间的距离 d i =1，此时整个只有一个子序列，对该序列进行直接插入排序，完成整个排序过程。
C#实现：
/// <summary>
/// 自定义工具类
/// </summary>
public static class Utilit
{
/// <summary>
/// 辅助输出排序结果：
/// </summary>
/// <param name="a"></param>
/// <param name="t"></param>
public static void Print(int[] a, int t)
{
string str = null;
for (int i = 0; i < a.Length; i++)
{
str += a[i].ToString() + " ";
}
Debug.Log("第" + t + "趟排序结果：" + str);
}
/// <summary>
/// 辅助生成排序结果
/// </summary>
/// <param name="max"></param>
/// <param name="length"></param>
/// <returns></returns>
public static int[] RandArray(int max, int length)
{
string str = null;
int[] a = new int[length];
for (int i = 0; i < a.Length; ++i)
{
a[i] = Random.Range(0, max);
str += a[i].ToString() + " ";
}
Debug.Log("随机生成的数组：" + str);
return a;
}
}
上方为产生随机数组与打印排序数组的工具类
希尔排序：
/// <summary>
/// 插入排序类
/// </summary>
public class InsertSort
{
/// <summary>
/// 3、希尔排序
/// </summary>
/// <param name="a"></param>
public static void ShellSort(int[] a)
{
int len = a.Length;
while (len != 0)
{
len = len / 2;
for (int i = 0; i < len; i++)//分组
{
for (int j = i + len; j < a.Length; j += len)
{
int k = j - len;//k为有序序列最后一个的位置
int temp = a[j];
while (k >= 0 && temp < a[k])
{
a[k + len] = a[k];
k -= len;
}
a[k + len] = temp;
}
Utilit.Print(a, i); //打印
}
}
}
}
测试用例：
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class _012_InsertSort : MonoBehaviour
{
void Start()
{
int[] a = Utilit.RandArray(20, 10);
//Debug.Log("------------直接插入排序----------------");
//InsertSort.StraightInsetSort(a); //直接插入排序
Debug.Log("------------折半插入排序----------------");
InsertSort.BInsertSort(a); //折半插入排序
//Debug.Log("------------希尔排序----------------");
//InsertSort.ShellSort(a);//希尔排序
}
}
输出结果：
注：
时间复杂度
当 d i =1 时，尽管这一趟希尔排序相当于直接插入排序，但因为此时序列的逆转数很小，所以移动次数相对于简单的直接插入排序而言也会减少。由此可见，希尔排序是一个较好的插入排序方法。希尔排序能迅速减少逆转数，尽管当间隔为 1 时，它相当于直接插入排序，但此时的关键字序列的逆转数已经很小，序列已经基本有序，使用的恰好是直接插入的最佳性质，它的时间复杂度为 O(n 1.5 )，比直接插入要好。
希尔排序对于中等规模（n<=1000）的序列具有较高的效率，且希尔排序算法简单，容易执行。因此很多排序应用程序都选用了希尔排序算法。算法稳定性
希尔排序的分析是一个复杂的问题，因为它的时间耗费是所取的“增量”序列的函数。
到目前为止，尚未有人求得一种最好的增量序列。但大量研究也得出了一些局部的结论。
在排序过程中，相同关键字记录的领先关系发生变化，则说明该 排序方法是不稳定的。
例如，待排序序列{2^，4，1，2}， 采用希尔排序，设 d 1 =2， {2，4，1，2}，得到一趟排序结果为{1，2，2^，4}，说明希尔排序法是不稳定的排序方法,两个2的顺序发生了变化。
插入排序类总结：
