cshapesearch.txt

这是Ｃ＃的查找算法

using System;
using System.Collections.Generic;
using System.Text;

namespace WebSystem.MathTool.Sort
{
    /// <summary>
    /// 用于排序的接口
    /// </summary>
    public abstract class Sortable
    {
        /// <summary>
        /// 排序的标志
        /// </summary>
        public int SortTag;
    }
}


using System;
using System.Collections.Generic;
using System.Text;

namespace WebSystem.MathTool.Sort
{
    /// <summary>
    /// 对集合进行排序、对排序后的列表进行查找
    /// </summary>
    public static class SortArray
    {
        /// <summary>
        /// 对实现Sortable的泛型List进行冒泡排序（简单实现）
        /// </summary>
        /// <typeparam name="T">实现Sortable的类</typeparam>
        /// <param name="thearray">原始泛型List</param>
        public static void Sort<T>(List<T> thearray) where T : Sortable
        {
            for (int ii = 0; ii < thearray.Count; ii++)
            {
                T tmpnode1 = thearray[ii];//当前轮次的起始节点
                T tmpnode2 = null;//暂存节点
                int tmp_count = 0;//变动的次数（对于高度有序列表，可以避免无效的循环）
                for (int jj = ii; jj < thearray.Count; jj++)
                {
                    if (thearray[jj].SortTag < tmpnode1.SortTag)//如果当前节点比起始节点小，就替换之
                    {
                        tmpnode2 = thearray[jj];
                        thearray[jj] = tmpnode1;
                        tmpnode1 = tmpnode2;
                        tmp_count++;//统计变动次数
                    }
                }
                if (tmp_count == 0)//如果变动次数为0，说明排序完成
                    return;
                thearray[ii] = tmpnode1;//替换当前轮次的节点
            }
        }

        /// <summary>
        /// 获取节点在列表中的位置
        /// </summary>
        /// <typeparam name="T">实现Sortable的类</typeparam>
        /// <param name="thearray">泛型List</param>
        /// <param name="item">节点</param>
        /// <returns>保存的位置，不存在就返回-1</returns>
        public static int GetIndex<T>(List<T> thearray, T item) where T : Sortable
        {
            if (thearray[0].SortTag > item.SortTag || thearray[thearray.Count - 1].SortTag < item.SortTag)//如果查找的节点在头尾节点标志之外，就返回-1
                return -1;
            if (thearray[0].SortTag == item.SortTag)//检查是否在头部
                return 0;
            if (thearray[thearray.Count - 1].SortTag == item.SortTag)//是否在尾部
                return thearray.Count - 1;
            int index_min = 0, index_max = thearray.Count - 1, index_middle = 0;//折半查找用到的3个变量
            while (true)
            {
                index_middle = (index_min + index_max) >> 1;//折半后的下标
                if (index_middle == index_min)//如果折半后的下标等于最小值的下标，说明已经查找结束，并且没有结果
                    return -1;
                if (thearray[index_middle].SortTag == item.SortTag)//结果刚好在折半后的节点，返回
                    return index_middle;
                if (thearray[index_middle].SortTag < item.SortTag)//如果折半后的节点的标志值小于目标节点的标志值，就修改左节点下标
                    index_min = index_middle;
                else//否则修改右节点下标
                    index_max = index_middle;
            }
            //return -1;
            //C#2.0的编译不错，检测到无法访问到的代码
        }
    }
}