首页 > 代码库 > [数据结构和算法]折半插入排序算法笔记

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

        /// <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;
                
            }
        }
<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>