## 二分法

1.算法设计

（1）初始化。令low=0，high=n-1。

（2）middle=(high-low)/2。

（3）判断low<=high是否成立，若成立，到第4步，否则算法结束。

（4）判断S[middle]与x的关系：若S[middle]>x，则x位于low~middle之间，令high=middle-1,；若S[middle]<x，则x位于middle~high之间，令low=middle+1；转第2步。若S[middle]==x，则搜索成功，退出。

2.图解

3.完整代码

#include<iostream>#include<algorithm>#include<cstdlib>#include<cstdio>using namespace std;const int M = 10000;int x, n, i;int s[M];int BinarySearch(int n, int s[], int x){    int low = 0;    int high = n - 1;    while (low <= high)    {        int middle = low +(high - low) / 2;        if (x < s[middle])            high = middle - 1;        else if (x > s[middle])            low = middle + 1;        else            return middle;    }    return -1;}int main(){    cout << "Please enter the number of these elements: ";    cin >> n;    cout << "Please enter the element: " << endl;    for (i = 0; i < n; i++)    {        cout << "Element " << i+1 << ": ";        cin >> s[i];    }    sort(s, s + n);    cout << "After sorted: " << endl;    for (i = 0; i < n; i++)        cout << s[i] << " ";    cout << endl;    cout << "Please enter the element that you want to find: " << endl;    cin >> x;    int ans = BinarySearch(n, s, x);    if (ans == -1)        cout << "Sorry, we can not find it.\n";    else        cout << "The answer is " << ans+1 << ".\n";    system("pause");    return 0;}

int BinarySearch(int n, int s[], int x,int low, int high){    if (low > high)        return -1;    int middle = (low + high) / 2;    if (x == s[middle])        return middle;    else if (x > s[middle])        return BinarySearch(n, s, x, middle + 1, high);    else        return BinarySearch(n, s, x, low, middle - 1);}

## 合并排序

1.算法原理

2.算法设计

（1）分解：将待排序列分解成大小相等的两个子序列；

（2）治理：将两个子序列进行合并排序；

（3）合并：将排好序的有序子序列进行合并，得到最终的序列。

3.完整代码

void Merge(int A[], int low, int mid, int high){    int *B = new int[high - low + 1];    int i = low, j = mid + 1, k = 0;    while (i <= mid && j <= high)    {        if (A[i] >= A[j])            B[k++] = A[j++];        else            B[k++] = A[i++];    }    while (i <= mid)        B[k++] = A[i++];//把剩下的元素复制到B中    while (j <= high)        B[k++] = A[j++];//把剩下的元素复制到B中    for (i = low,k=0; i <= high; i++)    {        A[i] = B[k++];    }    delete[] B;}void MergeSort(int A[], int low, int high){    if (low < high)    {        int mid = (low + high) / 2;//取中间点        MergeSort(A, low, mid);//对A[low:mid]中的元素进行合并排序        MergeSort(A, mid + 1, high);//对A[mid+1:high]中的元素进行合并排序        Merge(A, low, mid, high);//合并    }}

4.复杂度分析

（1）分解：O(1)；

（2）治理：2T(n/2)；

（3）合并：O(n)。

## 快速排序

1.算法原理

2.算法设计

（1）分解：先从数列中取出一个元素作为基准元素，以基准元素为准，将问题分解为两个子序列，使小于等于基准元素的子序列在左侧，大于基准元素的子序列在右侧。

（2）治理：对两个子序列进行快速排序。

（3）合并：将排好序的两个子序列合并在一起，得到原问题的解。由于排序是原地进行的，所以在排好序后，合并步骤无需做什么，序列就已经排好序了。

（1）取第一个元素；

（2）取最后一个元素；

（3）取中间位置的元素；

（4）取第一个、最后一个、中间位置元素三者的中位数；

（5）去第一个和最后一个之间位置的随机数k（low<=k<=high），选取R[k]做基准元素。

3.完整代码

int Partition(int r[], int low, int high){    int i = low, j = high;    int pivot = r[low];    while (i < j)    {        //当r[j]>pivot的时候，就继续由右往左寻找小于的元素        while (i<j && r[j]>pivot)            j--;        //跳出while循环说明找到了，再判断下i<j，然后交换i和j的元素，然后i++，再开始从左向右寻找r[i]>pivot的元素        if (i<j)            swap(r[i++], r[j]);        //当r[i]<pivot的时候，就继续加i，直到找到r[i]>pivot的时候，跳出wile循环        while (i < j && r[i] <= pivot)            i++;        //跳出while循环说明找到了，再判断下i<j，然后交换i和j的元素，然后j--，再开始从右向左寻找小于的元素        if (i<j)            swap(r[i], r[j--]);    }    return i;}void QuickSort(int R[], int low, int high){    //先从一堆元素中找到一个基准元素，然后以这个基准元素为准，左侧都小于它，右侧都大于它。然后再对左侧和右侧分别进行快速排序。    int mid;    if (low < high)    {        mid = Partition(R, low, high);        QuickSort(R, low, mid - 1);//左侧快速排序        QuickSort(R, mid + 1, high);//右侧快速排序    }}

4.复杂度分析

1.时间复杂度分析

（1）最好时间复杂度

①分解：O(n)；

②解决子问题：在最理想情况下，每次将问题划分为规模相当的两个子序列，也就是规模为n/2，即求解两个规模为n/2的子问题，所需时间为2T(n/2)；

③合并：没有任何操作，不需要时间复杂度。

（2）最坏时间复杂度

①分解：O(n)；

②解决子问题：在最坏情况下，基准元素的一侧无元素，另一次有1个规模为n-1的子问题，那么递归出来所需要的时间为T(n-1)；

③合并：没有任何操作，不需要时间复杂度。

（3）平均时间复杂度：O(nlogn)

5.算法优化扩展

int Partition2(int r[],int low, int high){    int i = low, j = high;    int pivot = r[low];    while (i < j)    {        while (i<j && r[j]>pivot)            j--;        while (i < j && r[i] <= pivot)            i++;        if (i < j)        {            swap(r[i++], r[j--]);        }    }    if (r[i] > pivot)    {        swap(r[i - 1], r[low]);        return i - 1;    }    swap(r[i], r[low]);    return i;}