[数据结构和算法]折半插入排序算法笔记

            /// <summary>
        

            /// 步骤:
        

            /// 1.记录当前待排元素
        

            /// 2.标记顺序表有序查找区域下界和上界
        

            /// 3.在顺序表有序查找区域中折半查找等待排序元素的位置
        

            /// 4.把顺序表有序查找区域的某些元素后移一位，以空出位置给等待排序的元素
        

            /// 5.在空出的位置填写当前排序元素
        

            /// </summary>
        

            /// <param name="elements"></param>
        

            static
            void SqListSort(int[] elements)

        {

            int low; // 有序区域下界

            int mid; // 有序区域中界

            int high;// 有序区域上界

            int standBy;//待排序元素

            // 从顺序表的第二个元素开始，直到结束，逐个做折半插入排序
        

            for (int i = 1; i < elements.Length; i++)

            {

                standBy = elements[i]; // 记录待排序元素

                low = 0;               // 标记下界

                high = i - 1;          // 标记上界

            // 在有序区域内折半查找待排元素合适位置
        

            while (low <= high)

                {

                    mid = (low + high) / 2;         // 记录中界

            if (standBy < elements[mid])    // 待排元素小于中界元素，说明在它适合的位置在前半区

                        high = mid - 1;             // 上界缩小

            else
        

                        low = mid + 1;              // 大于则说明在后半区，下界往前

                }

            // 把elem[high+1 .. i-1]的元素都往后移动一位，腾出位子
        

            for (int j = i - 1; j > high + 1; j--)

                {

                    elements[j + 1] = elements[j];

                }

            // 待排元素待插入位置为high+1
        

                elements[high + 1] = standBy;

            }

        }