用递归的算法求1，1，2，3，5，8.......的第30位数是多少，然后求这些数的和.
public int num(int i) //第i位数是多少 { if (i == 1) return 1; else if (i == 2) return 1; else return num(i - 1) + num(i - 2); } public int sum(int i) //所有数的和 { if (i == 1) return 1; else if (i == 2) return 2; else return sum(i - 1) + num(i); }
1到100内所有阶乘的和？
public int jiecheng(int n)//第n个数的阶乘 { if (n == 1) return 1; else if (n == 2) return 2; else return n * jiecheng(n - 1); } public int sumjiecheng(int n)//n个阶乘的和 { if (n == 1) return 1; else if (n == 2) return 3; else return jiecheng(n) + sumjiecheng(n - 1); }
查找算法
顺序查找
从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，知道两者相符，查到所要找的元素为止。否则就是表中没有要找的遇元素，查找不成功。
--平均要与表中一半以上元素进行比较，最坏情况下需要比较n次
--如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能顺序查找
--即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
二分法查找
---先确定待查找记录所在的范围，然后逐步缩小范围，知道找到或确认找不到该记录为止。
---前提：必须在具有顺序存储结构的有序表中进行。
---特点：比顺序查找方法效率高。最坏情况下，需要比较log2n.
public static int binarySearch(int[] a, int key) { 2: int low = 0; 3: int high = a.length - 1; 4: 5: while (low <= high) { 6: int mid =low+ (high-low) / 2; 7: int midVal = a[mid]; 8: 9: if (midVal < key) 10: low = mid + 1; 11: else if (midVal > key) 12: high = mid - 1; 13: else 14: return mid; // key found 15: } 16: return -(low + 1); // key not found. 17: }
冒泡排序
public class BubbleSort : ISort { public int[] Sort(int[] array) { if (array != null) { for (int i = 0; i < array.Length; i++) { for (int j = 1; j < array.Length - i; j++) { Swap(ref array[j - 1], ref array[j]); } } } return array; } public static void Swap(ref int int1, ref int int2) { if (int1 > int2) { int temp = int1; int1 = int2; int2 = temp; } } }
插入排序
采用的是以“玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1,R2,...,Ri-1已排好序，然后将Ri插入到已经排好序的诸记录的适当位置
最基本的插入排序是直接插入排序。（Strainght Insertion Sort)
直接插入排序
将待排序的记录Ri,插入到已排好序的记录表R1,r2,...,Ri-1中，得到一个新的、记录数增加1的有序表。直到所有的记录都插入完为止。
设待排序的记录顺序存放在数组R[1...n]中，在排序的某一刻，将记录序列分成两部分：
---R[1...i-1]:已排好序的有序部分；
---R[i-n]:未排好序的无序部分。
显然，在刚开始排序时，R[1]是已经排好序的。
7,4，-2,19,13,6
初始记录的关键字：7 4 -2 19 13 6
第一趟排序 : 4 7 -2 19 13 6
er :-2 4 7 19 13 6
public class InsertSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
int k = 1;//使用k变量，后面更好的扩展到Shell排序
for (int i = k; i < array.Length; i++)
{
int current = array[i];
int preIndex = i - k;
while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])
{
array[preIndex + k] = array[preIndex];
preIndex = preIndex - k;
}
array[preIndex + k] = current;
}
}
return array;
}
}
选择排序
每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止
初始关键字：7 4 -2 19 13 6
第一堂排序：-2 4 7 19 13 6
private static void SelectSort(int[] R) { int len = R.Length; int min = 0; for (int i = 0; i < len - 1; i++) { min = i; for (int j = i + 1; j < len - 1; j++) { if (R[min] > R[j]) { min = j; } } Swap(ref R[i], ref R[min]); } }
快速排序
是一类基于交换的排序，系统地交换反序的记录的偶对，直到不再有这样一来的偶对为止
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，在分别对这两部分记录进行下一趟排序，以达到整个序列有序。
设待排序的记录序列是R[s...t],在记录序列中任取一个记录（一般取R[s].key为基准重新排列其余的所有记录，方法是：
所有关键字比基准小的放R[s]之前；
所有关键字比基准大的放R[s]之后。
以R[s].key最后所在位置i作为分界，将序列R[s...t]分割成两个子序列，称为一趟快速排序
private static void QuickSort(int[] R, int low, int high) { int pivotLoc = 0; if(low<high) { pivotLoc = Partition(R, low, high); QuickSort(R, low, pivotLoc - 1); QuickSort(R, pivotLoc + 1, high); } } private static int Partition(int[] R, int low, int high) { int temp = R[low]; while (low < high) { while (low < high && temp <= R[high]) { high--; } R[low] = R[high]; while (low < high && temp >= R[low]) { low++; } R[high] = R[low]; } R[low] = temp; return low; }
//快速非递归排序 public static void QuickSort(int[] R, int Low, int High, Stack<int> stack) { int low = Low; int high = High; int temp = R[low]; while (high > low) { while (low < high && temp <= R[high]) { high--; } if (high > low) { R[low] = R[high]; R[high] = temp; } while (low < high && temp >= R[low]) { low++; } if (high > low) { R[high] = R[low]; R[low] = temp; } if (low == high) { if (Low < low - 1) { stack.Push(Low); stack.Push(low - 1); } if (High > low + 1) { stack.Push(low + 1); stack.Push(High); } } } } 测试代码： static void Main(string[] args) { int[] arry = new int[] { 10, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76 }; Stack<int> s=new Stack<int>(); s.Push(0); s.Push(arryk.Length - 1); while (s.Count > 0) { int low = s.Pop(); int high = s.Pop(); if (low > high) { temp = low; low = high; high = temp; } QuickSort(arryk, low, high, s); } Console.ReadLine(); } 通过对10万条随机数据进行递归和非递归排序后发现，非递归方法的速度是递归方法速度的40倍左右。
5 . 一个无序的数组，如何通过一个函数取出最大值和最小值，要求时间复杂度最低和空间最少 具体算法如下： private static int[] GetMaxMin(int[] R) { int len=R.Length; int min = R[0]; int max = R[0]; for (int i = 1; i < len;i++ ) { if (min > R[i]) { min = R[i]; } if (max < R[i]) { max = R[i]; } } int[] res = new int[2]; res[0] = min; res[1] = max; return res; } 6 对于已知数组，随机存储一百个数，把奇数放左边，偶数放右边，具体算法如下： private static void SortNumber(int[] R) { int high = R.Length - 1; int low = 0; int temp = R[low]; while (low < high) { while(low<high&&R[high]%2==0) { high--; } R[low] = R[high]; while (low < high && R[low] % 2 == 1) { low++; } R[high] = R[low]; } R[low] = temp; }