(一)算法——冒泡排序、选择排序

╰+攻爆jí腚メ 2022-07-18 01:48 217阅读 0赞

强烈推荐一个大神的人工智能的教程：[http://www.captainbed.net/zhanghan][http_www.captainbed.net_zhanghan]

简介

算法是解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。——摘自百度百科

为什么要用算法呢？假设现在给出三个数A,B,C，请你找出这三个数中最大的一个数。答案不止一种，不过我猜，有一部分人要选择if...else方法，一步一步的逐个比较，找出最大的数之后将最大值放到一个变量中，然后将该最大值输出出来！答案，没有绝对的对与错，而有适合不适合！现在只是给出了三个数，当我们给出100个数，1000个数的时候呢？如果简单的使用if...else去解决问题是不是超级累呀？对选择排序有一定了解的程序猿，可能会想出一个较为简单的方法，假设最大值！ 拿3个数为例 ，代码如下，这样做就将比较局部化，只需考虑相邻的两个数,不用再去管有多少个数，max只要一直走下去就能保证自己是最大的！

<span style="font-size:18px;"><span style="font-size:18px;">int a,b,c,max;  //定义变量
    max = a;        //假设最大值为a
      if(b>max){    //当b>max时将b赋值给max
         max = b;
      }else if(c>max){   //当c>max时将c赋值给max
         max = c; 
      }
       print max;  //打印最大值</span></span>

选择排序(从小到大排序)

1.原理

①从第2位开始寻找最小数与第一位交换  
     ②从第3位开始寻找最小数与第2位交换  
     ③直到第n个元素和第n-1个元素相比为止

2.示例

我们随机生成10个1-100之间的整数，见结果展示中的第0次排序后即为自动生成的10个整数。

3.代码实现

//引用
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Diagnostics;   //计算耗时类

static void Main(string[] args)
            {
                Stopwatch sw = new Stopwatch();
                sw.Start(); //开始计时
                int temp;       //中间变量
                int index = 0;  //最小数的脚标
                Random example = new Random();  //随机数
                int[] num = new int[10];        //包含10个元素的数组
                string unSort = "第0次排序后：";  //未排序前序列
                string Sort = "";   //排序后的序列
                
               //生成随机数
                for (int numCount = 0; numCount < 10; numCount++)
                {
                     int number = example.Next(1, 100);
                     num[numCount] = number;
                     unSort = unSort +"  "+ num[numCount];                
                }
                unSort = unSort + "\r\n\r\n\r\n";    //换行
                Console.Write(unSort);    //输出未排序前的序列
    
                //从小到大排序
                for (int i = 0; i < num.Count()-1; i++)
                {
                    index = i;
                    for (int j = i+1; j < num.Count(); j++)
                    {
                        //寻找从第j位开始最小数
                        if (num[j]<num[index])
                        {
                            index = j;
                        }
                    }
                    //第i个数和最小的数交换
                    temp = num[i];
                    num[i] = num[index];
                    num[index] = temp;
    
                    //排一次序输出一次排序结果
                    Sort = "";
                    Sort = "第" + (i + 1) + "次排序后：";                
                    for (int k = 0; k < num.Count(); k++)
                    {
                        Sort =Sort+ "  " + num[k];                   
                    }
                    Sort = Sort + "\r\n\r\n\r\n";
                    Console.Write(Sort);
    
                }
                sw.Stop();  //计时结束
                TimeSpan ts2 = sw.Elapsed;  //计算该算法耗时
                Console.Write("总共花费{0}ms.", ts2.TotalMilliseconds); //输出该算法耗时
                Console.ReadKey();
            }

4.用时

![Center][]

5.结果展示

说明：绿色框起来的数是待交换的数，红色标出来的是两个数进行交换，交换后会得到下一行的排序结果。看着排序的结果特别像一个倒三角。

![Center 1][]

6.稳定性

因为第i个值具体和哪个数进行交换是不确定的，假如有两个相同的数值，就拿20来举个例子。现在序列中有两个相同的值20，假如经过一系列的交换后，前边的20跑到了后边20的后边。这个时候两个相同的值实际上可以看作是交换了位置。所以这种算法是不稳定的。

冒泡排序(从小到大排序)

1.原理

①从第一对开始相邻的两个数两两进行比较，若第一个数比第二个数大，则两个数进行交换，依次对所有元素进行相邻两数两两比较，此时得到最后一个数是该序列中最大的数。

②排完第一轮之后，最后一个数则是有序区，除第一个数之外前边所有数是无序区(参考结果展示图，绿色标志的为无序区，剩下的为有序区)。再对无序区进行第一步的操作，依次会得到相应的有序区和无序区。

③依次对无序区进行第①步的操作直至所有序列为有序区

2.示例

我们随机生成10个1-100之间的整数，采用冒泡排序方法进行排序。

3.代码实现

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Diagnostics;   //计算耗时类
    
    namespace 冒泡排序算法
    {
        class Program
        {
            static void Main(string[] args)
            {           
                Stopwatch sw = new Stopwatch(); //计算耗时类
                sw.Start();
                int temp;
                Random example = new Random();
                int[] num = new int[10];    //包含10个元素的数组
                //生成随机数
                for (int rnd = 0; rnd < num.Length-1; rnd++)
                {
                    num[rnd] = example.Next(1, 100);    //随机生成10个数放入数组中
                }
                //打印输出排序前的数组
                Console.Write("排序前数组：");
                foreach (int item in num)
                {
                    Console.Write(item + "  ");
                }
                Console.WriteLine("\r\n\r\n");
    
                //排序
                for (int outside = 0; outside < num.Length-1; outside++)
                {
                    for (int inside = 0; inside < num.Length-1-outside; inside++)
                    {
                        if (num[inside]>num[inside+1])
                        {
                            temp = num[inside];
                            num[inside] = num[inside + 1];
                            num[inside + 1] = temp;
                        }
                    }
                    Console.Write("第" + (outside + 1)+"次排序后：");
                    foreach (int item in num)
                    {
                        Console.Write(item + "  ");
                    }
                    Console.WriteLine("\r\n\r\n");
                }
                sw.Stop();
                TimeSpan ts2 = sw.Elapsed;
                Console.Write("总共花费{0}ms.", ts2.TotalMilliseconds); //输出该算法耗时
                Console.ReadKey();
            }
        }
    }

4.用时

![Center 2][]

5.结果展示

![Center 3][]

6.稳定性

该算法的原理是相邻的两个数进行比较，假设相邻的两个数是相等的，那他就不会进行交换。所以这个算法是稳定的。

[http_www.captainbed.net_zhanghan]: http://www.captainbed.net/zhanghan
[Center]: /images/20220717/26aa5f3e18794fc082b3bd247b69a5a9.png
[Center 1]: /images/20220717/2c530f0b5e984000bfd57d3459f20c13.png
[Center 2]: /images/20220717/959d2bafa6f845c0b8f9c9806f2d39d7.png
[Center 3]: /images/20220717/11f5c5d016bc4271b83f82ecccc3fc43.png