二分查找
问题描述
二分查找又称为折半查找，它要求待查找的数据元素必须是按关键字大小有序排列的。给定已排好序的n个元素s1,…,sn，现要在这n个元素中找出一特定元素x。 首先较容易想到使用顺序查找方法，逐个比较s1,…,sn，直至找出元素x或搜索遍整个序列后确定x不在其中。显然，该方法没有很好地利用n个元素已排好序这个条件。因此，在最坏情况下，顺序查找方法需要O(n)次比较。
算法思想
假定元素序列已经由小到大排好序，将有序序列分成规模大致相等的两部分，然后取中间元素与特定查找元素x进行比较，如果x等于中间元素，则算法终止；如果x小于中间元素，则在序列的左半部继续查找，即在序列的左半部重复分解和治理操作；否则，在序列的右半部继续查找，即在序列的右半部重复分解和治理操作。可见，二分查找算法重复利用了元素间的次序关系。
构造实例
创建数组并随机赋值，定义low为数组左边界high为数组右边界（数组长度-1）middle为数组长度的一半。middle=(low+high)/2，即指示中间元素；我们需要通过代码来每次折半查找我们需要的元素值。
实现方法
1、两种非递归
twoFind1()
int twoFind1(int A[], int len, int K) { int low = 0, high = len - 1,middle; if (low > high) return -2; while (low <= high)//包含等于的情况 { middle = (low + high) / 2; if (K == A[middle]) return middle; else if (K > A[middle]) low = middle + 1; else high = middle - 1; } return -1; } twoFind2() int twoFind2(int A[], int len, int K) { int low = 0, high = len - 1,middle; if (low > high) return -2; while (low < high)//不含等于的情况，并在最后做判断 { middle = (low + high) / 2; if (K == A[middle]) return middle; else if (K > A[middle]) low = middle + 1; else high = middle - 1; } if (low == high && A[low] == K) return low; return -1; }
2、递归算法
//递归二分查找算法 int twoFind3(int A[], int k, int low, int high) { int middle; if (low > high) return -1;//递归结束条件 middle = (low + high) / 2; if (low==high && A[middle] == k) return middle; if (low < high) { if (A[middle] < k) return twoFind3(A, k, middle + 1, high); else if(A[middle]==k) return middle; else return twoFind3(A, k, 0, middle - 1); } return -1; }
时间复杂度
二、合并排序
算法思想
合并排序是采用分治策略实现对n个元素进行排序的算法，是分治法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略，其计算过程分为三大步： （1）分解：将待排序元素分成大小大致相同的两个子序列。 （2）求解子问题：用合并排序法分别对两个子序列递归地进行排序。 （3）合并：将排好序的有序子序列进行合并，得到符合要求的有序序列。
合并方法
设置三个工作指针i，j，k。其中，i和j指示两个待排序序列中当前需比较的元素，k指向辅助数组B中待放置元素的位置。比较A[i]和A[j]的大小关系，如果A[i]小于等于A[j]，则B[k]=A[i]，同时将指针i和k分别推进一步；反之，B[k]=A[j]，同时将指针j和k分别推进一步。如此反复，直到其中一个序列为空。最后，将非空序列中的剩余元素按原次序全部放到辅助数组B的尾部。
算法描述
非递归形式
void Merge(int A[]，int low，int middle，int high) { int i,j,k; int *B=new int[high-low+1]; i=low; j=middle+1; k=low; while(i<=middle&&j<=high) //两个子序列非空 if(A[i]<=A[j]) B[k++]=A[i++]; else B[k++]=A[j++]; while (i<=middle) B[k++]=A[i++]; while (j<=high) B[k++]=A[j++]; for(i=low;i<=high;i++) A[i++]=B[i++]; }
递归形式
void MergeSort (int A[]，int low，int high) { int middle; if (low<high) { middle=(low+high)/2; //取中点 MergeSort(A,low,middle); MergeSort(A,middle+1,high); Merge(A,low,middle,high); //合并 } }
时间复杂度
求得T(n)=nT(1)+nlogn=n+nlogn，即合并排序算法的时间复杂性为O(nlogn)
三、快速排序
算法思想
通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。
快排分治体现
1、分解
在A[low:high]中选定一个元素作为基准元素(P)，以此基准元素为标准将待排序序列划分为两个子序列并使序列A[low:P-1]中所有元素的值均小于等于A[P]，序列A[P+1:high]中所有元素的值均大于等于A[P]。
2、求解子问题 对子序列A[low:P-1]和A[P+1:high],分别通过递归调用快速排序算法来进行排序。
3、合并 就地排序。
对于基准元素P可以采取以下五种方法：
（a）取第一个元素。 （b）取最后一个元素。 （c）取位于中间位置的元素。 （d）“三者取中的规则”。 （e）取位于low和high之间的随机数，用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high)，用A[P]作为基准，这相当于强迫R[low:high]中的元素是随机分布的。
划分方法的构造实例
图示助理解
以第一个元素作为基准元素
具体代码实现
tips：完整代码，可复制后直接使用
#include<iostream> using namespace std; //交换函数swap void swap1(int& a, int& b) { int temp = a; a = b; b = temp; } //做一个把数组分两半的函数 int sortSecond(int A[], int low, int high) { int P = A[high];//基数选择右边界 while (low < high) { while (low < high && A[low] <= P) low++;//左边部分小的跳过 if (low < high){ swap1(A[low], A[high--]);//大的扔到后面并使右边界减一 } while (low<high && A[high]>=P) high--;//右边大的跳过 if (low < high) { swap1(A[low++], A[high]);//小的扔到前面并使左边界加一 } } return low;//此时low=high } void fastSort(int A[], int low, int high) { if (low > high) return;//递归结束条件 low>high int v = sortSecond(A, low, high); fastSort(A, low, v - 1);//对左区间递归排序 fastSort(A, v + 1, high);//对右区间递归排序 } int main() { int A[9] = {4,3,1,2,4,9,5,8,6}; int len = sizeof(A) / sizeof(A[0]); cout << "排序前数组为：\t" << endl; for (int i = 0; i < len; i++) { cout << A[i] << " "; } cout << endl; fastSort(A, 0, len-1);//时间复杂度 平均情况O(nlogn)，最坏情况O(n^2) cout << "快速排序后数组为：\t" << endl; for (int i = 0; i < len; i++) { cout << A[i] << " "; } }
我选择的是以最右边的元素作为基准元素，所以先和基准元素左边的值作比较，如果A[low]<=P，进行low++操作，反之交换数据并让让右边界减一，这是因为右半部分是和P作比较，所以没必要把判断过的数据重复判断，直到low!<high，返回low的值，而且不难想到此时low=high。
运行效果
时间复杂度
