一些面试常见的算法

毕业了,为了找工作,研究了一下,希望可以对大家有帮助
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
           // int[] mask = {19,1,5,6,7,8,3,2,10,44,55,22,99};
            
           // //selectsort(mask);//选择排序
           // //pipsort(mask);//冒泡排序
           // quicksort(mask, 0, mask.Length - 1);//选择排序
           // print(mask);
           // //折半查找
           // int index = hfind(mask, 99, 0, mask.Length - 1);
           
           //Console.Write(index);
           //Console.Read();            //1、1、2、3、5、8、13、21、34......求第30位数
            //int num = getNUM(9);
            //Console.Write(num);
            //Console.Read();            //两个字符数组,第一个数组全是英文,第二个英文加*(通配符)
            //求是否匹配
            //char[] mask = "abcdefghi".ToCharArray();
            //char[] match = "*ef*".ToCharArray();
            //bool bl = matchEX(mask, match);
            //Console.Write(bl);
            //Console.Read();            //单词倒叙
            //i   am  a   good    man----> man good a am i
            Console.Write(restr("i   am  a   good    man"));
            Console.Read();
        }        static void selectsort(int[] a)
        {
            //选择排序
            //首先选择a[0]为起始选择项
            int len = a.Length;
            for (int i = 0; i <= len - 2; i++)
            {
                for (int j = i + 1; j <= len - 1; j++)//依次作比较
                {
                    if (a[i] > a[j])
                    {
                        change(ref a[i], ref a[j]);//按引用传递,否则不会完成交换
                    }
                }
            }
        }        static void change(ref int a, ref int b)//交换两个数
        {
            int temp;
            temp = a;
            a = b;
            b = temp;
        }
        static void print(int[] a)
        {
            foreach (int b in a)
            {
                Console.WriteLine(b);
               
            }
            //Console.Read();
        }       
        static void pipsort(int[] a)
        {
            //冒泡排序就是两两交换
            int len = a.Length - 1;
            for (int i = 0; i < len; i++)
            {                for (int j = 0; j < len - i; j++)
                {
                    if (a[j] > a[j + 1])
                    {
                        change(ref a[j], ref a[j+1]);
                    }
                }
            }
        }
        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="a"></param>
        /// <param name="left">左下标</param>
        /// <param name="right">右下标</param>
        static void quicksort(int[] a,int left ,int right)
        {
            //快速排序
           
            if (left < right)
            {
                int mid = a[left];//将a[0]设置为中值
                int i = left;
                int j = right;//前后的下标,如果是c++ 应该是指针
                while (i < j)
                {
                    while (a[j] > mid)
                    {
                        //找到第一个小于mid的数,从后面找
                        j--;
                    }
                    while (a[i] < mid)
                    {
                        //找到第一个大于mid的数,从前面找
                        i++;
                    }
                    change(ref a[i], ref a[j]);
                }
                a[i] = mid;
                quicksort(a, left, i - 1);
                quicksort(a, j + 1, right);
            }
        }
        /// <summary>
        /// 折半查找
        /// </summary>
        /// <param name="a">输入的原始数组,已经排序,从小到大</param>
        /// <param name="b">要查找的数组</param>
        /// <returns>数组的下标</returns>
        static int hfind(int[] a,int b,int left , int right)
        {
            int i = (left + right)/2; //中间的那个下标
            if (a[i] == b)
            {
                return i;
            }
            else if (a[i] > b)//说明在前面一段
            {
                return hfind(a, b, left, i - 1);
            }
            else
            {
                return hfind(a, b, i+1, right);
            }
        }        static int getNUM(int x)
        {
            //1、1、2、3、5、8、13、21、34......求第30位数
            //分析:1+1 = 2 1+2 = 2+3 =5 即 n + (n+1) = (n+2)
            //递归的退出条件,也是起始条件
            if (x == 1 || x == 2)
            {
                return 1;
            }
            //第x个数
            return getNUM(x - 2) + getNUM(x - 1);
        }        static bool matchEX(char[] mask, char[] match)
        {
            int i = 0;
            int j = 0;//数组下标            while (mask[i] == match[j])
            {
                if(i == mask.Length -1)
                {
                    return true;
                }
                i++;
                j++;
            }
            if (match[j] != '*')
            {
                return false;
            }
            else//如果遇见匹配列是"星"需要特殊处理
            {
                if (j  == match.Length -1)//*后没有字符,返回真
                {
                    return true;
                }
                 //首先找到mask中第一个和星后字符匹配的地方
                while (i < mask.Length - 1)
                {
                    if (mask[i] == match[j + 1])//match[j+1]是*后第一个字符的位置
                    {
                        char[] tempmask = new char[mask.Length - i-1];//i后第一个既是,
                        char[] tempmatch = new char[match.Length - j-2];//j后第一个已经比较过,从第二个开始
                        Array.Copy(mask, i + 1, tempmask, 0, mask.Length - i -1);
                        Array.Copy(match, j +2, tempmatch, 0, match.Length - j - 2);//构造子数组
                       
                        if (matchEX(tempmask, tempmatch))//递归
                        {
                            return true;
                        }
                        else
                        {
                            return false;
                        }
                    }                    i++;
                }                return false;
            }
        }       static private string restr(string str)
        {
           string [] strs = str.Split(new Char[] { ' ' },StringSplitOptions.RemoveEmptyEntries);
            str = "";
           for (int i = strs.Length-1; i >= 0; i--)
           {
               str += strs[i] + " "; 
           }           return str;
        }
    }
}