读一读

广度优先搜索是图的一种算法,一是可以确定有没有到达的路径,而是如果有那么这个路径就是最短路径。就像水波那样,先从原点向周围一圈一圈的搜索(假设一圈有好多数据),没有才向更外圈搜索。


class Vertex {
    public string data;
    public bool isVisited;

    public Vertex(string d) {
        data = d;
        isVisited = false;
    }
}

class Program
{
    static Dictionary<string, Vertex[]> dict = new Dictionary<string, Vertex[]>();
    static void Main(string[] args)
    {
        Vertex A = new Vertex("Bom");
        Vertex B = new Vertex("Tom");
        Vertex C = new Vertex("Chicai");
        Vertex D = new Vertex("Marry");

        //构建关系图,谁是谁的好友
        //I是原点,AB为第一圈,D为第二圈,C为第三圈
        dict.Add("I", new Vertex[] { A, B });
        dict.Add("Bom", new Vertex[] { D });
        dict.Add("Tom", new Vertex[] { D });
        dict.Add("Marry", new Vertex[] { A,B,C });
        dict.Add("Chicai", new Vertex[] { D });

        Search("Chicai");

        Console.ReadKey();

    }

    static void Search(string name) {
        Queue<Vertex> queue = new Queue<Vertex>();
        Vertex[] datas;
        dict.TryGetValue("I", out datas);
        foreach (Vertex x in datas) {
            queue.Enqueue(x);
        }

        while (queue.Count > 0) {
            Vertex x = queue.Dequeue();
            if (x.isVisited) {
                continue;
            }
            x.isVisited = true;
            if (x.data == name)
            {
                Console.WriteLine("找到了:" + name);
                return;
            }
            else {
                Console.WriteLine(x.data);
                Vertex[] vertex;
                dict.TryGetValue(x.data, out vertex);
                foreach (Vertex v in vertex) {
                        queue.Enqueue(v);
                }
            }
        }

        Console.WriteLine("找不到啊");
    }
}


这里是一个找好友的游戏,通过好友来找好友,例如找一个叫Chicai的好友,首先从我自己这里找AB(Bom,Tom)都不是,那么就将他们的好友也加进队列中进行查找,这时候就有了D(Marry),发现D也不是,那么将Marry的好友也加进队列,这时候才有了C(Chicai),这时候就找到了。如果好友关系网中都没有这个人(那就是队列为空了)。


散列表也叫做字典(哈希),这个就熟悉了吧。它通过将字符串等映射到数组的索引中,实现了通过字符串一下子就查找到目标值O(1)。散列表有着数组,散列函数,通过散列函数将字符串转换成数组对应的索引,一个良好的散列函数会有较少的冲突(就是两个不同的字符串对应到了同一个索引),这时候会在该索引位置生成一个链表,如果链表(冲突)很长,说明这个散列函数不好。散列表的查找、删除、插入等操作都很快,就是填装因子大到一定程度时>0.7(数组的位置不够装了),需要重构散列表时比较耗时。

很典型的一个例子就是DNS的解析,每个域名都对应着一个ip,通过域名查找ip,若是不适用散列表,查找时间为O(n),全世界有多少个域名,想想就觉得可怕。

还有就是网站的缓存,通过域名来获取到对应的缓存页面。


快速排序是一种比选择排序快得多的算法,当然是数据量大的时候,主要思想就是利用一个参考值,将大的组分成两个小的组,一个组都比参考值小,一个组都比参考值大。一直分,分到不能再分,再把每个组和参考值都合并起来


static void Main(string[] args)
{
    List<int> list = new List<int>();
    Random r = new Random();
    for (int i = 0; i < 100000; i++) {
        list.Add(r.Next(1, 10000));
    }
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    List<int> sort = quickSort(list);
    stopwatch.Stop();
    foreach (int data in sort) {
        Console.WriteLine(data);
    }

    Console.WriteLine("运行时间:" + stopwatch.ElapsedMilliseconds);

    Console.ReadKey();
}

static List<int> quickSort(List<int> datas) {
    int length = datas.Count;
    //只有一个元素或则没有元素就返回自身(已经排序好了)
    if (length < 2) {
        return datas;
    }

    //随机一个参考数
    Random r = new Random();
    int random_index = r.Next(0, length);
    int val = datas[random_index];
    datas.RemoveAt(random_index);
    List<int> left = new List<int>();//比参考值小的组
    List<int> right = new List<int>();//比参考值大的组

    foreach (int data in datas) {
        if (data < val)
        {
            left.Add(data);
        }
        else {
            right.Add(data);
        }
    }

    left = quickSort(left);
    right = quickSort(right);
    
    //合并起来
    left.Add(val);
    left.AddRange(right);
    return left;
}


快速排序的运行时间:O( nlog(n) )

10W个随机数据排序运行时间:207ms(不知道是不是用了List的原因,还是写法问题,总觉得慢了)

详情看:吃菜网-选择排序和快速排序


就是讲一个大的问题,分割成小的问题,在将这个小的问题分割成更小的问题

再解决这些问题,达到基准线,再退出

例如:二分法和快速排序

二分法查找每次查找都缩小了一半的范围

快速排序每次寻找一个参考点,分成两个小的排序组,再分,直到每个小的组都排序好(只有一个元素或则空了),再合成为一个组

适合小的,也适合大的


栈的调用虽然很方便,但是需要大量的栈空间来存储函数的调用


static void Main(string[] args)
{
    Console.WriteLine(Mul(5));
    Console.ReadKey();
}

//计算1到n的累积
static int Mul(int n) {
    if (n == 1) {
        return 1;//等于1的时候就该退出啦
    }
    return n * Mul(n - 1);
}


递归主要就是自己调用自己,提供一个出口来退出,停止自己调用自己

说下 n * Mul(n - 1) ,例如这里的 5

5*Mul(4) = 5*4*Mul(3) = 5*4*3*Mul(2) = 5*4*3*2*Mul(1)

这时候最后一个Mul(1)直接返回的1,没有调用自己,程序就退出了

返回 5*4*3*2*1的值


最简单粗暴的一个排序,遍历循环比较每一个值,发现更小的就交换位置


static void Main(string[] args)
{
    int[] datas = new int[100000];
    Random r = new Random();
    for (int i = 0; i < 100000; i++) {
        datas[i] = r.Next(1, 10000);
    }

    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    int[] newdatas = Sort(datas);
    stopwatch.Stop();
    foreach (int data in newdatas) {
        Console.WriteLine(data);
    }

    Console.WriteLine("用时:" + stopwatch.ElapsedMilliseconds);
    Console.ReadKey();
}

static int[] Sort(int[] datas) {
    int length = datas.Length;
    int[] newArr = new int[datas.Length];
    for (int x = 0; x < length; x++) {
        newArr[x] = datas[x];//复制数组到新数组
    }
    
    //对新数组进行排序
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            if (newArr[j] < newArr[i]) {
                //对比发现后面值较小时,交换值
                int temp = newArr[i];
                newArr[i] = newArr[j];
                newArr[j] = temp;
            }
        }
    }
    return newArr;//返回新的数组(排序好的)
}


对于冒泡排序的执行次数为(n+n-1+n-2...+1) = n/2(n+1)

所以运行时间为 O(n2)

模拟排序10W条数据用时:24439ms


class Data {
    public int id;
    public string Name;
}

class Program
{
    static Dictionary<int,Data> list;

    static void Main(string[] args)
    {
        list = new Dictionary<int, Data>();
        for (int i = 1; i <= 100; i++) {
            Data data = new Data();
            data.id = i;
            data.Name = "Name" + i;
            list.Add(i,data);
        }

        while (true) {
            Console.WriteLine("输入你要查找的数字");
            string input = Console.ReadLine();
            int num;
            Int32.TryParse(input, out num);
            int index = searchNum(num, 1, list.Count);
            Console.WriteLine(index);
        }
    }

    static int searchNum(int value, int from, int to) {

        int result = -1;

        int temp = (int)Math.Floor((double)(from + to) / 2);

        if (temp < 1 || temp > list.Count) {
            return -1;
        }

        //获取中间元素的值
        int tempVal = list[temp].id;
        if (tempVal == value) {
            return temp;
        }

        if (from == to)  {//找不到
            return -1;
        }

        if (tempVal > value) {
            result = searchNum(value, from, temp-1);
        }

        if (tempVal < value) {
            result = searchNum(value, temp+1, to);
        }

        return result;
    }
}


运行时间为:O(log(n))

对于一个已经排好序的列表,使用中间值的方式来比较值

如果小了,就往左边查找,缩小一半的范围

同样的这样循环,一直对半缩小范围,直到查找到值或找不到(范围内只有一个值了)