首页 > 代码库 > Chapter 2 算法基础
Chapter 2 算法基础
-------------------注明----------------
以下内容来自于《算法导论》 lz新手，存在各种错误以及各种不合理的地方望大家指出
----------------------------------------
2.1 插入排序
核心： 将一个数插入到已经排好序的有序数列中，从而得到一个新的、个数加1的有序数列
形象描述：有两堆牌，左手一堆已经排好序，右手一堆未排好，将右手中的牌一张一张取出来，放到左手这堆牌中（保证每次放进去都使左手牌仍有序）
实现代码（以下按升序排序）：为了以后偷懒，采用了泛型
static void InsertSort<T>(List<T> array) where T:IComparable { for(int i=1;i<array.Count;i++) //将第i个数插入已排好序的[0...i-1]中 { T key = array[i]; int position = i; //用于记录将要插入的位置 for(int j=i;j>=0;j--) //将要前面数与要插入数进行比较,如果比key大,往后移一位 { if(array[j].CompareTo(key)>0) //由于T实现了IComparable接口 { array[j + 1] = array[j]; position = j; } } array[position] = key; } }
采用的测试代码如下：(以int类型为示范)
static void Main(string[] args) { Random rnd = new Random(); List<int> array=new List<int>(); for (int i = 0; i < 10;i++ ) { array.Add(rnd.Next(50)); } Console.WriteLine("排序前:"); foreach (int i in array) Console.Write("{0} ",i); Console.WriteLine(); InsertSort<int>(array); Console.WriteLine("排序后:"); foreach (int i in array) Console.Write("{0} ", i); Console.ReadKey(); }
其中一次运行结果如下：
-----练习----
2.1-2：只需将array[j].CompareTo(key)>0改为array[j].CompareTo(key)<0即可
2.1-3：线性查找(以int为例，此外略微改动了下原题)，代码如下：
static int FindNum(List<int> array,int num) { int position = -1; //记录下标作为返回值,未找到则为-1 for(int i=0;i<array.Count;i++) { if (array[i] == num) { position = i; break; //为了返回结果为第一次找到该值的下标 } } return position; }
2.1-4：二进制相加问题的体现，2个n位的二进制相加，结果可能依旧为n位，或者n+1位
核心：将二进制数存进数组，如0111,也按常规数组思路，从左到右代表数组的下标(即0存储在A[0]中)，根据对应项相加，遇2进1的原则。
代码如下：(此代码有待改善,以下代码必须要求a,b的位数相同)
static List<int> AddBinary(List<int> a,List<int> b) { int[] c = new int[a.Count+1]; //数组c用于存储相加后的结果,长度为n+1 for(int i=a.Count-1;i>=0;i--) { //此处为两个二进数对应项及进位的值共同相加 if (a[i] + b[i] + c[i + 1] >= 2) //进位的情况 { c[i + 1] = a[i] + b[i]+c[i+1] - 2; c[i]++; } else //不进位的情况 c[i + 1] = a[i] + b[i]+c[i+1]; } List<int> list = new List<int>(); list.AddRange(c); return list; //返回相加结果 }
测试代码如下：
static void Main(string[] args) { int n = 6; Random rnd = new Random(); List<int> a = new List<int>(); List<int> b = new List<int>(); for(int i=0;i<n;i++) { a.Add(rnd.Next(2)); b.Add(rnd.Next(2)); } Console.Write("二进数A="); foreach(int i in a) Console.Write("{0}",i); Console.WriteLine(); Console.Write("二进数B="); foreach (int i in b) Console.Write("{0}", i); Console.WriteLine(); List<int> c = AddBinary(a, b); Console.Write(" A+B="); foreach(int i in c) Console.Write("{0}", i); Console.ReadKey(); }
一次测试实例结果：
---------------
2.2 分析算法
判断算法优劣，根据算法所需要的资源----大部分情况下，我们采用运行时间
往往取运行时间的增长量级或增长率---即最高次作为衡量一个算法的"优劣"
-------练习-------
2.2-2 选择排序：找出A中最小元素将其与A[0]交换位置,在找出除A[0]外最小元素与A[1]交换，一直重复到n-1
形象描述：在一堆鞋子中，找出尺码最小的往外扔，依次进行直到扔完（升序），扔完后鞋子叠起来的次序便是排好序的
排序实现代码如下：
static void SelectSort<T>(List<T> array)where T:IComparable { int position=0; for(int i=0;i<array.Count-1;i++) { position = i; //用于记录i之后最小值的下标 for(int j=i+1;j<array.Count;j++) //遍历找出i之后最小值 { if (array[j].CompareTo(array[position])<0) position = j; } T temp = array[position]; //交换位置 array[position] = array[i]; array[i] = temp; } }
运行情况如下：
最坏最好情况分析：由于两个for循坏无论在什么前提下，均执行次数一致(可以看到没有break等语句在Code中)，所以最好最坏情况的运行时间均为θ(n^2)。
2.2-3 线性查找问题：最坏n次，最好1次。最坏和平均情况的运行时间均为θ(n)。
--------------------
2.3 设计算法
分治法：简单的说就是把问题拆拆拆（前提：拆了的只是规模比原来小）！！！拆到你感觉解起来so easy的时候那就解吧，解完后再递归回去，麻烦点的话还可能要有怎么合并的考虑。
实例：递归排序---不断对半砍直到每个都只为1个，还需要排吗？哦啦，但是还需要考虑合并的问题啦。两堆有序之间合并采用直接一一对比！
合并函数(为了能用泛型,采用不含哨兵的方法---如何对于一个T设置一个很大的值还木有想到>.<!)：
static void Merge<T>(List<T> array,int p,int q,int r)where T:IComparable { int len1 = q - p + 1, n1 = 0; //用于临时存储两边元素的数组的参数 int len2 = r - q, n2 = 0; T[] arr1 = new T[len1]; //建立两个临时数组,用于储存数组值 T[] arr2 = new T[len2]; for (int i = 0; i < len1; i++) //将array值拷贝到临时存放数组 arr1[i] = array[p + i]; for (int j = 0; j < len2; j++) arr2[j] = array[j + q + 1]; for(int k=p;k<r+1;k++) //将两个数组中的值按升序放回到array数组中 { if (arr1[n1].CompareTo(arr2[n2]) < 0) array[k] = arr1[n1++]; else array[k] = arr2[n2++]; if(n1==len1) //此处为arr1数组已全部取完后的处理方法 { for(int m=k+1;m<r+1;m++) array[m] = arr2[n2++]; break; } if(n2==len2) { for (int m = k+1; m < r + 1; m++) array[m] = arr1[n1++]; break; } } }
递归排序函数：
static void MergeSort<T>(List<T> array, int p, int r) where T : IComparable { if(p<r) { int q = (p + r) / 2; MergeSort(array, p, q); MergeSort(array, q + 1, r); Merge(array, p, q, r); } }
运行时间为O(nlogn)---由于合并函数的缘故，对于数量少的情况反而会更加耗时
-------练习-------
2.3-3 显然当n=2时，T(2)=2lg2=2---成立
假设当n=2k时，T(2k)=2klg(2k)成立，只需证T(2k+1)=2k+1=2k+1lg2k+1
由 T(2k+1)=2T(2k)+2k+1=2*2klg(2k)+2k+1=2k+1(lg2k+lg2)=2k+1lg2k+1
从而得证。
2.3-4 插入排序的递归模式，插入函数+递归函数
插入函数如下：(和插入排序进行对比，少了个for语句---由递归完成)
static void Insert(List<int> array,int p,int q) { int temp = array[q], position = q; //将array[q]插入到p..q-1中,使之依然满足升序 for(int i=q-1;i>=p;i--) { if (array[i] > temp) { array[i + 1] = array[i]; position = i; } else //为了减少运行步数,此处采用了break break; } array[position] = temp; }
递归函数
static void InsertMerge(List<int> array,int p,int r) { int q; if(p<r) { q = r - 1; InsertMerge(array, p, q); Insert(array, p, r); //此处注意为r,如果改为q的话,则最后一项未调用排序函数 } }
最坏运行时间的递归式为：
2.3-5 二分查找(以下Code只适用于已排好序的情况)
static int BinarySearch(List<int> array,int p,int r,int num) { int q = (r + p) / 2; if (num == array[q]) return q; else if (num > array[q]&&q<r) return BinarySearch(array, q+1, r, num); else if(num<array[q]&&q>p) return BinarySearch(array, p, q-1, num); return -1; }
2.3-6 不能，原因：利用二分查找改良的插入排序：但是由于插入位置后续的数组均要向后移动，因此最坏情况运行时间仍旧为θ(n2)
2.3-7 确定n个整数的集合S中是否存在两个数之和刚好为x的元素
method1：先将S中集合进行排序，采用递归或者后续其他排序(时间为θ(nlgn))，然后再利用二分查找+for进行寻找(该方法时间也为θ(nlgn))
递归排序代码与前面的完全相同，略过
二分查找+遍历循坏：
static List<int> BinaryFind(List<int> array,int num) { List<int> list = new List<int>(2); for(int i=0;i<array.Count-1;i++) //将0...n-1分别与后续的进行相加 { int begin = i + 1,end = array.Count - 1; //进行二分查找的首尾 int mid=(begin+end)/2; while(begin<=end) //循环的终止条件,即二分查找的终止条件 { if (array[i] + array[mid] == num) //找到的情况 { list.Add(array[i]); list.Add(array[mid]); return list; } else if (array[i] + array[mid] > num) end = mid-1; else begin = mid+1; mid = (begin + end) / 2; } } list.Add(-1); list.Add(-1); //找不到的情况 return list; }
method2：此方法来源于一篇博客(当时做的笔记，未写引用，忘见谅)
step 1:对集合S进行排序，可以采用归并排序算法
step 2:对S中每一个元素a，将b=x-a构造一个新的集合S‘，并对S’进行排序
step 3:去除S和S‘中重复的数据
step 4:将S和S‘按照大小进行归并，组成新的集合T，若干T中有两队及以上两个连续相等数据，说明集合S中存在两个整数其和等于x。
- 例如：S={7,10,5,4,2,5}，设x=11，执行过程如下：
- 对S进行排序，S={2,4,5,5,7,10}。
- S‘={9,7,6,6,4,1},排序后S’={1,4,6,6,7,9}。
- 去除S和S‘中重复的数据后S={2,4,5,7,10}，S‘={1,4,6,7,9}
归纳S和S‘组成新集合T={1,2,4,4,5,6,7,7,9,10}，可以看出集合T中存在两对连续相等数据4和7，二者存在集合S中，满足4+7=11。
step 1根据上述递归排序，step2~step4的Code如下：
static List<int> FindSum(List<int> array,int num) { List<int> arr = new List<int>(); List<int> list = new List<int>(); for (int i = 0; i < array.Count; i++) //一个新数组,每个元素b[i]=num-a[i] arr.Add(num - array[i]); for (int i = 0; i < array.Count-1; i++) { if (array[i] == array[i + 1]) array.RemoveAt(i); if (arr[i] == arr[i + 1]) arr.RemoveAt(i); } for (int i = 0, j = arr.Count - 1; i < array.Count || j >= 0;) //将arr和array组合成新集合 { if(i==array.Count) { for (int k = j; k >= 0; k--) list.Add(arr[k]); break; } if(j==-1) { for(int k=i;k<array.Count;k++) list.Add(array[k]); break; } if (array[i] > arr[j]) list.Add(arr[j--]); else list.Add(array[i++]); } int count = 0; //用于记录有多少对重复 List<int> result = new List<int>(); for(int i=0;i<list.Count-1;i++) { if (list[i] == list[i + 1]) { count++; result.Add(list[i]); } } if (count >= 2) return result; else { result.Clear(); result.Add(-1); return result; } }
测试代码如下：
static void Main(string[] args) { List<int> array = new List<int> { 12, 3, 10, 1, 2, 4, 5, 8, 6, 7}; Random rnd = new Random(); int num =rnd.Next(25); foreach (int a in array) Console.Write("{0} ", a); Console.WriteLine(); Console.WriteLine("num={0}", num); MergeSort<int>(array, 0, array.Count - 1); List<int> result = FindSum(array, num); if (result[0] == -1) Console.WriteLine("该数组中找不到!"); else { Console.WriteLine("此数组中存在两数之和为{0},且存在于以下几个数中", num); foreach (int a in result) Console.Write("{0} ", a); } Console.ReadKey(); }
其中一次运行结果如下：
此方法的原理：b=x-a，如果数组S和S‘中均有a,b则显然会出现两个连续相等数据(并且此时a,b恰好为所需值)(注,由于此方法同时将b=x-a,b==a的情况也包含进去，从而会出现单数次重复数据---如果排除此情况必然为双数次重复)
----------------
思考题：待续
Chapter 2 算法基础