快速排序

维基百科详细说明

 public static void QuickSort(int[] numbers, int left, int right)        {            if (left < right)            {                int middle = numbers[(left + right) / 2];                int i = left - 1;                int j = right + 1;                while (true)                {                    while (numbers[++i] < middle)                    {                    }                    while (numbers[--j] > middle)                    {                    }                    if (i >= j)                        break;                    Swap(numbers, i, j);                }                QuickSort(numbers, left, i - 1);                QuickSort(numbers, j + 1, right);            }        }    public static void Swap(int[] arr, int i, int j)        {            int temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;        }

冒泡排序

public static void BubbleSort(int[] arr)        {            int n = arr.Length;            for (int i = 0; i < n - 1; i++)            {                for (int j = i + 1; j < n; j++)                {                    if (arr[i] > arr[j])                    {                        int temp;                        temp = arr[i];                        arr[i] = arr[j];                        arr[j] = temp;                    }                }            }        }

选择排序

 public static void SelectionSort(int[] arr)        {            int smallIndex;            int pass;            int j;            int temp;            int n = arr.Length;            for (pass = 0; pass < n - 1; pass++)            {                // 假定最小值初始时是arr[pass]=1st                smallIndex = pass;                // 遍历子列表，从arr[pass+1]到arr[n-1]                //j从pass+1开始，因为从0到pass已经是有序的了                for (j = pass + 1; j < n; j++)                {                    //如果发现小元素，把当前元素的索引赋值给最小值                    //这其实就是一个找最小元素的过程                    if (arr[j] < arr[smallIndex])                    {                        smallIndex = j;                    }                }                //交换                temp = arr[pass];                arr[pass] = arr[smallIndex];                arr[smallIndex] = temp;            }        }

插入排序

public static void InsertSort(int[] arr)        {            int i, j;            int n = arr.Length;            int target;            //假定第一个元素被放到了正确的位置上            //这样，仅需遍历1 - n-1            for (i = 1; i < n; i++)            {                j = i;                target = arr[i];                while (j > 0 && target < arr[j - 1])                {                    arr[j] = arr[j - 1];                    j--;                }                arr[j] = target;            }        }

二分查找

递归写法：

public static int BinarySearch(int[] arr, int low, int high, int key)        {            int mid = low + (high - low) / 2;            if (low > high)                return -1;            else            {                if (arr[mid] == key)                    return mid;                else if (arr[mid] > key)                    return BinarySearch(arr, low, mid - 1, key);                else                    return BinarySearch(arr, mid + 1, high, key);            }        }

循环写法：

public static int BinarySearch(int[] data, int low, int high, int x)        {            int mid;//中间位置            if (low > high)            {                return -1;            }            while (low <= high)            {                mid = (low + high) / 2;                if (x == data[mid])                {                    return mid;                }                else if (data[mid] < x)                {                    low = mid + 1;                }                else if (data[mid] > x)                {                    high = mid - 1;                }            }            return -1;        }

求质数算法

定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.

证明: 如果n不是素数, 则由定义n有一个因子d满足1<d<n.

如果d大于sqrt(n), 则n/d是满足1<n/d<=sqrt(n)的一个因子.

尝试从2到\sqrt{N}的整数是否整除N。

素数定义（维基百科）

/*埃拉托斯特尼篩法*/        public static bool IsPrime(int x)        {            int i;            if (x <= 1)/*1不是質數，且不考慮負整數與0,故輸入x<=1時輸出為假*/            {                return false;            }            for (i = 2; i * i <= x; ++i)            {                if (x % i == 0)/*若整除時輸出為假，否則輸出為真*/                {                    return false;                }            }            return true;        }

求最大公约数算法

最大公约数（维基百科）

1、查找约数法．

先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数．

例如，求12和30的最大公约数． 12的约数有：1、2、3、4、6、12；

30的约数有：1、2、3、5、6、10、15、30．

12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数．

2 、更相减损术

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。

如下:

91 49

42 49

42 7

35 7

28 7

21 7

14 7

7  7

这里得到的7就叫做“等数”,91和49都是这等数的重叠(即倍数),故7为其公约数.而7和7的最大公约数就是7,(7,7)=7,所以(91,49)=(42,7)=(7,7)=7

 //更相减损法       public static int Gcd(int a, int b)       {           while (a != b)           {               if (a > b)                   a -= b;               else                   b -= a;           }           return a;       }

3、辗转相除法．

又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法

当两个数都较大时，采用辗转相除法比较方便．其方法是：

以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数．

例如：求4453和5767的最大公约数时，可作如下除法．

5767÷4453＝1余1314 

4453÷1314＝3余511  

1314÷511＝2余292  

511÷292＝1余219  

292÷219＝1余73

  //辗转相除法--递归       public static int Gcd(int a, int b)        {            if (b == 0)                return a;            else                return Gcd(b, a % b);        }        //辗转相除法--纯循环       public static int GcdIterate(int a, int b)       {           int r;           while (b != 0)           {               r = a % b;               a = b;               b = r;           }           return a;       }

最小公倍数

最小公倍数（维基百科）

public static float minGongBeiShu(int n1, int n2)       {           int temp = Math.Max(n1, n2);           n2 = Math.Min(n1, n2);//n2中存放两个数中最小的           n1 = temp;//n1中存放两个数中最大的           int product = n1 * n2;//求两个数的乘积           while (n2 != 0)           {               n1 = n1 > n2 ? n1 : n2;//使n1中的数大于n2中的数               int m = n1 % n2;               n1 = n2;               n2 = m;           }           return (product / n1);//最小公倍数       }