插入排序：折半插入排序（稳定）

【算法思想】从关于查找的讨论中可知，对于有序表进行折半查找，其性能优于顺序查找。所以，可以将折半查找用于在有序记录 r[0..len-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>
    /// 2、折半插入排序
    /// </summary>
    /// <param name="a"></param>
    public static void BInsertSort(int[] a)
    {
        int insertNum;//要插入的数
        int len = a.Length;//数组长度

        for (int i = 1; i < len; i++)
        {
            insertNum = a[i];
            int low = 0;
            int high = i - 1;

            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (insertNum < a[mid])
                {
                    high = mid - 1;//插入点在低半区
                }
                else
                {
                    low = mid + 1;//插入点在高半区
                }
            }

            for (int j = i - 1; j >= low; j--)
            {
                a[j + 1] = a[j];//后移元素
            }
            a[low] = insertNum;

            Utilit.Print(a, i);
        }
    }

}

测试用例：

public class _012_InsertSort : MonoBehaviour
{


    void Start()
    {
        int[] a = Utilit.RandArray(20, 10);

      
        Debug.Log("------------折半插入排序----------------");
        InsertSort.BInsertSort(a); //折半插入排序


    }

}

输出结果：

插入排序：折半插入排序

注：

【算法分析】采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第 i 个元素时，设 i=2 j ,则需进行 log 2 i 次比较，因此插入 n-1 个元素的平均关键字的比较次数为 nlog 2 n。当 n 较大时，折半插入排序法的比较
次数比直接插入排序的最差情况要好很多，但比其最好情况要差。
虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级为O(nlog 2 n)，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n^ 2 )。

image.png