文档介绍：快速排序（Quick Sort）
思想：每一轮选取1个基准数X，把大于X的元素放在X右边，小于X的元素放在X左边，此时序列被划分为X左边的子序列和X右边的子序列，分别对两个子序列再进行相同的操作，直到整个序列有序。
*
二分搜索与快速排序
*
void quick_sort(int s[], int l, int r)  
{  
    if (l < r)  
    {  
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1  
        int i = l, j = r, x = s[l];  
        while (i < j)  
        {  
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数  
                j--;    
            if(i < j)   
                s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数  
                i++;    
            if(i < j)   
                s[j--] = s[i];  
        }  
        s[i] = x;  
        quick_sort(s, l, i - 1); // 递归调用   
        quick_sort(s, i + 1, r);  
    }  
}
*
二分搜索与快速排序
*
重要应用：查找第k大元素
利用快速排序的思想，我们可以在平均复杂度O(n)的时间复杂度内求出一个序列的第K大元素。
思想：对于每一轮基准数归位后，可以根据要查找元素跟基准数的相对位置在对应子序列中进行查找。
*
二分搜索与快速排序
*
二分搜索 简单定义
在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在那个部分并调整上下界，重复直到找到目标元素。
时间复杂度：O(logn),优于直接顺序查找O(n)
*
二分搜索与快速排序
*
int Bsearch(int array[], int low, int high, int target)
{
while(low <= high)
{
int mid = (low + high)/2;
if (array[mid] > target)
high = mid - 1;
else if (array[mid] < target)
low = mid + 1;
else
return mid; //找到目标数,返回它的下标
}
return -1;//没有找到目标数
}
*
二分搜索与快速排序
*
二分查找求下界或上界
但若数组中有多个元素都是target，它只会返回中间那一个target的下标，这样使用效果不理想，能不能求出值等于target的完整区间呢（由于已经排好序，相等的值会排在一起）？
所以一般用二分查找求下界或上界
*
二分搜索与快速排序
*
求下界： 找到有序数组a1,a2,...,an中第一个大于等于k的元素的位置
low=1; high=n;
while (high-low>1) //不断缩小答案区间(low,high]
{
mid=(low+high) >> 1;
if (a[mid]>=k)
high=mid;
else
low=mid;
}
cout<<high<<endl;
*
二分搜索与快速排序
*
STL
Lower_bound(first, last, val) 算法返回非递减序列 [first, last) 中第一个大于等于val的位置
Upper_bound(first, last, val) 算法返回非递减序列 [first, last) 中第一个大于val的位置
#include <algorithm>
sort(a+1,a+n+1);
pos=lower_bound(a+1,a+n+1,x)-a;
*
二分搜索与快速排序
*
重要模型：
这个算法除了