查找算法的实现和比较

我不是女神ヾ 2022-09-19 05:24 35阅读 0赞

一直想比较一下查找算法，最近工作之余实现了一下算法，做了一下对比

现在有一链表

static ArrayList \_serverList = new ArrayList();里面的数据为int,保证其值从小到大排列。当然，我们在写入数据时用查找算法找到相应位置写入就行了。

1：顺序比较，这个太土，就是一个一个比，这个我就不说了，也没有实现

2：折半居中查找，如果是10000000个数据，查找一次要节约0.2秒左右的时间

下面是程序

public class ServerList  
    \{  
        \#region  
        static ArrayList \_serverList = new ArrayList();  
        int leftFind = 0;  
        int rightFind = 0;  
        int serverIndex = -1;  
        public ServerList()  
        \{ \}

public bool AddServer(int serverId)  
        \{  
            try  
            \{  
                lock (\_serverList)  
                \{  
                    int iGetServer;  
                    iGetServer = GetServer(serverId);  
                    if (\_serverList.Count == 0)  
                        \_serverList.Add(serverId);  
                    else if (serverId == iGetServer)  
                    \{  
                        return false;  
                        //Console.WriteLine("不能添加，已经有相同的Server");  
                    \}  
                    else if (serverId < (int)(\_serverList\[0\]))  
                        \_serverList.Insert(0, serverId);  
                    else if (serverId > (int)(\_serverList\[\_serverList.Count - 1\]))  
                        \_serverList.Insert(\_serverList.Count, serverId);  
                    else \_serverList.Insert(serverIndex, serverId);  
                \}  
            \}  
            catch  
            \{  
                return false;  
            \}  
            return true;  
        \}

public bool DeleteServer(int serverId)  
        \{  
            try  
            \{  
                lock (\_serverList)  
                \{  
                    int iGetServer;  
                    iGetServer = GetServer(serverId);  
                    if (serverIndex >= 0)  
                        \_serverList.Remove(iGetServer);  
                \}  
            \}  
            catch  
            \{  
                return false;  
            \}  
            return true;  
        \}

public int GetServer(int serverId)  
        \{  
            leftFind = 0;  
            rightFind = \_serverList.Count - 1;  
            serverIndex = -1;  
            if (\_serverList.Count == 0)  
                return -1;  
            if (\_serverList.Count == 1 || serverId == (int)(\_serverList\[0\]))  
            \{  
                serverIndex = 0;  
                return (int)(\_serverList\[0\]);  
            \}  
            if (serverId < (int)(\_serverList\[0\]) || serverId >= (int)(\_serverList\[\_serverList.Count - 1\]))  
            \{  
                serverIndex = \_serverList.Count - 1;  
                return (int)(\_serverList\[\_serverList.Count - 1\]);  
            \}  
            int iServerIndex = \_serverList.Count / 2;  
            return GetMax(iServerIndex, serverId);  
        \}

internal int GetMax(int index, int serverId)  
        \{  
            if ((int)(\_serverList\[index\]) == serverId)  
            \{  
                serverIndex = index;  
                return (int)(\_serverList\[index\]);  
            \}  
            if (rightFind - leftFind <= 1)  
            \{  
                serverIndex = rightFind;  
                return (int)(\_serverList\[rightFind\]);  
            \}  
            if (serverId > (int)(\_serverList\[index\]))  
            \{  
                leftFind = index;  
                index = index + (rightFind - index) / 2;  
            \}  
            if (serverId < (int)(\_serverList\[index\]))  
            \{  
                rightFind = index;  
                index = index - (index - leftFind) / 2;  
            \}  
            return GetMax(index, serverId);  
        \}

public string GetServerString()  
        \{  
            if (\_serverList.Count == 0)  
                return "It not have any Server";  
            string strServerList = "";  
            for (int i = 0; i < \_serverList.Count; i++)  
            \{  
                strServerList += \_serverList\[i\].ToString() + ",";  
            \}  
            strServerList = strServerList.Trim(new char\[\] \{ ',' \});  
            return strServerList;  
        \}  
        \#endregion

###  ###