C#常用的算法

一.二分法

注：一定是有序的数组，才可以使用这种算法，如果数组没有排序则先进行排序后再调用此方法。

二分顾名思义，就是将一组数据对半分开(比如左右两部分，下面用左右数组表示)，从中间位置开始查找，

如果中间这个值正是咱们要找的值则直接返回这个值(或者索引)，如果没有找到，那么去判断中间的这个值和咱们要找的值哪个大，

如果中间值比咱们要找的值大，则将之前分开的数组的左面的数组再进行对半分开，递归直到找到咱们要的那个值才会结束，反之亦然，

但是如果就是没有咱们找的值那么岂不是死循环了嘛，

所以要加判断，如果递归到开始索引大于结束索引，也就是查到最后了还是没有找到匹配的值，则退出。

这种搜索算法每一次比较都使搜索范围缩小一半，这样对于大数据量的数组，极大的提升了查找效率。

private void button1_Click(object sender, EventArgs e)

        {

            int[] arry = { 8, 15, 19, 23, 26, 31, 40, 65, 91 };

            //测试  要找的数字是15

            int key = 15;

            //查找数并返回 若有，返回该数，没有则返回-1

            int rr = BinarySearch(arry, 0, arry.Length - 1, key);

        }

        /// <summary>

        /// 二分法查找指定值

        /// </summary>

        /// <param name="arr">目标数组</param>

        /// <param name="start">开始索引</param>

        /// <param name="end">结束索引</param>

        /// <param name="key">要查找的关键字</param>

        /// <returns></returns>

        public static int BinarySearch(int[] arr, int start, int end, int key)

        {

            int mid = (start + end) / 2;

            if (start > end)

                return -1;//查找不到返回-1

            else

            {

                Console.WriteLine(arr[mid]);//监测查找了哪些数字

                if (arr[mid] == key)

                    return mid;//若查找到，返回该数

                else if (arr[mid] > key)

                    return BinarySearch(arr, start, mid - 1, key);

                else return BinarySearch(arr, mid + 1, end, key);

            }

        }

二.递归

1.递归方法一直会调用自己直到某些条件满足,也就是说一定要有出口;
2.递归方法会有一些参数,而它会把这些新的参数值传递给自己;(自己调自己);
递归通常用于:　　①.阶乘（）　　②.斐波拉切数列（公式如果F0=0并且F1=1那么Fn=F(n-1)+F(n-2);）

1.阶乘（从1到n的连续自然数相乘的积）
注意最高支持到31阶乘：

 static void Main(string[] args)

        {

            int n;

            int.TryParse(Console.ReadLine(), out n);

            Console.WriteLine(Factorial(n));

            Console.ReadKey();

        }

        static int Factorial(int n)

        {

            if (n == 0)

            {

                return 1;

            }

            return n * Factorial(n - 1);

        }

2.斐波拉切数列（斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……这个数列从第三项开始,每一项都等于前两项之和.）

public static int Foo(int i)

        {

            if (i <= 0)

            {

                return 0;

            }

            else if (i > 0 && i <= 2)

            {

                return 1;

            }

            else

            {

                return Foo(i - 1) + Foo(i - 2);

            }

        }

三.冒泡排序

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

int[] nums = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

for (int i = 0; i < nums.Length - 1; i++)

{

    for (int j = 0; j < nums.Length-1-i; j++)

    {

        if (nums[j] > nums[j + 1])

        {

            int temp = nums[j];

            nums[j] = nums[j + 1];

            nums[j + 1] = temp;

        }

    }

}

//打印数组

for (int i = 0; i < nums.Length; i++)

{

    Console.WriteLine(nums[i]);

}

Console.ReadKey();

四.不使用中间变量交换两个数

常用的有三种方法，加减法，乘除法，异或法:

1.加减法，这个是最容易的想到的，不过需要注意的，如果在处理浮点型数字的时候可能会精度丢失:

 　 a=a+b;

    b=a-b;

    a=a-b;

2.乘除法，和加减法类似，也会有精度丢失，不过出现的一个问题是除数不能为0：

    a=a*b;

    b=a/b;

    a=a/b;

3.异或法,这个需要记住的一点就是变量a异或b的异或值异或b等于a:

    a=a^b;

    b=a^b;

    a=a^b;

五.插入排序

插入排序实际上把待排序的数列分为了两部分，一部分已排好序，另一部分待排序。我们下面还是以一组实际数据为例进行讲解。例如采用直接插入排序算法将无序表{3,1,7,5,2,4,9,6}进行升序排序的过程为：

首先需要明确待排序的数列由两部分组成，一部分是已排好序的部分，另一部分是待排序的部分；
接着我们每次选择待排序的部分的第 1 个元素，分别与前面的元素进行比较。当大于前面的元素时，可以直接进入已排好序的部分；当小于前面的元素时，需要把这个元素拿出来，将前面的元素后移一位，继续与前面的元素相比，直到比较完数组的第 1 个元素或者出现一个元素小于我们拿出来的这个元素，这时停止比较、移动，直接把这个元素放到当时的空位上；
一直重复步骤 2，当待排序的部分已经没有元素可进行插入时，停止操作，当前的数列为已排好序的数列。

使用场景

在数组元素规模较小的时候，插入排序法的运行效率很高。其经常用在一些其他排序方法中（比如归并排序以及快速排序）来对排序进行优化。
不同于选择排序法，当一个数组几乎有序的时候，插入排序法所需要的时间要比其他的排序法快得多。因此插入排序法的排序时间取决于数组元素的初始顺序，在最好的情况下，插入排序法运行时间能达到线性级别。

class Program

{

    //插入排序法

    public static void insertSort(int[] array)

    {

        //for循环：i作为指针，进行从左到右扫描数据的工作

        //指针i从1开始扫描，因为i=0时指针左侧无元素

        for (int i = 1; i < array.Length; i++)

        {

            //temp作为指针键值

            int temp = array[i];

            //新建变量j，从i开始向左扫描已经有序的元素，并与temp比较

            //若temp小于扫描元素，则将j指针元素向右移位腾出空间

            int j = i;

            while (j > 0 && array[j - 1] > temp)

            {

                array[j] = array[j - 1];

                j--;

            }

            //循环完成后将temp放在j指针位置，完成本次插入

            array[j] = temp;

        }

    }

    //打印数组

    public static void printArray(int[] array)

    {

        foreach (int item in array)

        {

            Console.Write(item + "\t");

        }

        Console.WriteLine();

    }

    //主函数入口

    static void Main(string[] args)

    {

        int[] array = new int[10] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

        printArray(array);

        insertSort(array);

        printArray(array);

        Console.ReadKey();

    }

}

六.选择排序

每次从后面找到最小或最大的数，进行位移排序。

数组 int [] array = [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];

第一位 i=0

最小值下标 minIndex = 0，最小值 min=11

从后面查找比 11 小的数，找到第下标位 8，值为1，

进行交换,交换后 [1, 39, 35, 30, 7, 36, 22, 13, 11, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];

第二位 i=1，

最小值下标 minIndex = 1，最小值 min=39,

从后面查找比 39 小且最小的数，找到下标为 13，值为 5，

进行交换，交换后 [1, 5, 35, 30, 7, 36, 22, 13, 11, 38, 26, 18, 12, 39, 45, 32, 6, 21, 42, 23];

public static void ReSort(ref int[] array)

        {

            for (int i = 0; i < array.Length; i++)

            {

                int min = array[i];     //设定第i位为最小值

                int minIndex = i;       //最小值下标

                for (int j = i; j < array.Length; j++)  //从第i为开始找出最小的数

                {

                    if (array[j] < array[minIndex])     //重新存储最小值和下标

                    {

                        min = array[j];

                        minIndex = j;

                    }

                }

                if (array[i] != array[minIndex])        //如果到比第i为更小的数，则发生交换。找不到则不改变

                {

                    array[minIndex] = array[i];

                    array[i] = min;

                }

            }

        }

七.快速排序

快速排序是从冒泡排序演变而来，快速排序之所以快，是因为使用了分治法。

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

快速排序是在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列的一边，比它晓得元素移动到数列的另一边，从而把数列拆解成两个部分。

public class QuickSort

    {

        public static void Test()

        {

            int[] arr = { -9, 78, 0, 23, -567, 70 };

            Sort(arr,0,arr.Length-1);

            System.Console.WriteLine(string.Join(",",arr));

        }

        public static void  Sort(int[] arr ,int left,int right)

        {

            int l = left;

            int r = right;

            //中间值

            int middle = arr[(l + r) / 2];

            //temp临时变量

            int temp = 0;

            //while循环的目的是让比middle值小的放在左边 比middle大的值放在右边

            while (l<r)

            {

                //在middle的左边一直找，找到大于等于middle的值才退出

                while (arr[l]<middle)

                {

                    l++;

                }

                //在middle的右边边一直找，找到小于等于middle的值才退出

                while (arr[r]>middle)

                {

                    r -= 1;

                }

                //如果l>=说明middle的左边两边的值，已按照左边全是小于等于middle的值，右边都是大于middle的值

                if (l>=r)

                {

                    break;

                }

                //交换

                temp = arr[l];

                arr[l] = arr[r];

                arr[r] = temp;

                //如果交换完之后，发现这个arr[l]==middle这个值 ,-- 前移

                if (arr[l]==middle)

                {

                    r -= 1;

                }

                //如果交换完之后，发现这个arr[r]==middle这个值 ,++ 后移

                if (arr[r]==middle)

                {

                    l++;

                }

            }

            //如果l==r，必须l++,r--,否则会出现栈溢出

            if (l==r)

            {

                l += 1;

                r -= 1;

            }

            //向左递归

            if (left<r)

            {

                Sort(arr, left, r);

            }

            //向右递归

            if (right>l)

            {

                Sort(arr, l, right);

            }

        }

    }

八.在一个给定的从1到100的整型数组中，如何快速找到缺失的数字

九如何找到一个给定的整型数组中的重复数字？

十在一个未排序的整型数组中，如何找到最大和最小的数字？

十一在一个整型数组中，如何找到一个所有成对的数字，满足它们的和等于一个给定的数字？

十二如果一个数组包含多个重复元素，如何找到这些重复的数字？

十三用C# 实现从一个给定数组中删除重复元素？

十四如何利用快速排序对一个整型数组进行排序？

十五如何从一个数组中删除重复元素？

十六用 C#如何实现数组反转？

十七如何输出字符串中的重复字符？

十八如何判断两个字符串是否互为回文？

十九如何从字符串中输出第一个不重复字符？

static void Main(string[] args)

        {

            string str = "ABCDCBAbbb";

            var index = FirstUniqChar(str);

            var charStr= str[index];

        }

        public static int FirstUniqChar(String s)

        {

            char[] temp = s.ToCharArray();

            int length = temp.Length;

            int j, i;

            int result = 0;

            for (i = 0; i < length; i++)

            {

                for (j = 0; j < length; j++)

                {

                    if (i == j) { continue; }

                    if (temp[i] == temp[j])

                    {

                        break;

                    }

                }

                if (j == length)

                {

                    result = i;

                    break;

                }

            }

            if (i == length)

            {

                result = -1;

            }

            return result;

        }

二十如何使用递归实现字符串反转?

二十一如何在字符串中找到重复字符？

二十二如何计算给定字符传中特定字符出现的次数？

二十三如何找到一个字符串的全排列？

二十四在不使用任何库方法的情况下如何反转给定语句中的单词？

二十五如何判断两个字符串是否互为旋转？

/// <summary>

        ///a="cdab"，b="abcd"，返回true；

        ///a="1ab2"，b="ab12"，返回false；

        ///a="2ab1"，b="ab12"，返回true。

        /// </summary>

        /// <param name="args"></param>

        static void Main(string[] args)

        {

            string a = "cdab";

            string b = "abcd";

            var aResult = IsRotation2(a, b);

            a = "1ab2"; b = "ab12"; // 返回false；

            var bResult = IsRotation2(a, b);

        }

        public static bool IsRotation2(String a, String b)

        {

            if (a == null || b == null || a.Length != b.Length)

            {

                return false;

            }

            String b2 = b + b;

            return IndexOf(b2, a, 0) > -1;

        }

        private static int IndexOf(String b2, String a, int index)

        {

            char[] source = b2.ToCharArray();

            char[] target = a.ToCharArray();

            return Func(source, 0, source.Length, target, 0, target.Length, index);

        }

        private static int Func(char[] source, int sourceOffset, int sourceCount,

                            char[] target, int targetOffset, int targetCount,

                            int fromIndex)

        {

            if (fromIndex >= sourceCount)

            {

                return (targetCount == 0 ? sourceCount : -1);

            }

            if (fromIndex < 0)

            {

                fromIndex = 0;

            }

            if (targetCount == 0)

            {

                return fromIndex;

            }

            char first = target[targetOffset];

            int max = sourceOffset + (sourceCount - targetCount);

            for (int i = sourceOffset + fromIndex; i <= max; i++)

            {

                if (source[i] != first)

                {

                    while (++i <= max && source[i] != first) ;

                }

                if (i <= max)

                {

                    int j = i + 1;

                    int end = j + targetCount - 1;

                    for (int k = targetOffset + 1; j < end && source[j]

                            == target[k]; j++, k++) ;

                    if (j == end)

                    {

                        return i - sourceOffset;

                    }

                }

            }

            return -1;

        }

巴特西