快速排序算法和二分查找

我们先来做一道简单的题：

题目描述：

利用快速排序算法将读入的N个数从小到大排序后输出。（N≤10^5）

很简单是不是？ sort()函数扫一遍，只要数据不是特别的大，就能过。

但是你如果不用sort()函数呢，你会做吗？

快速排序说：我可以～

快速排序算法：

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1e6+1;
int n,a[MAX];

void qsort(int begin ,int end){ 
    int temp = a[(begin+end)/2];                 //   取中间数
    int i = begin;                         //定义两个指针，从数组的两端扫
    int j = end;
    while(i <= j){
        while(a[i] < temp)  i++;       //这两个循环结束后会得到一对不满足左小右大的下标
        while(a[j] > temp)  j--;
        if(i<=j){
            swap(a[i],a[j]);
                i++;
                j--;
        }
    }  
    if(i < end)  qsort(i,end);
    if(j > begin)  qsort(begin,j);        //在左右两边分别再递归这个过程，排序完成   
}

可能大家会说：有了sort()还那么麻烦干嘛？
那你再看一道题：
输入n(n<5000000且n为奇数)个数字ai(ai<1e9)输出第k小的数字，最小的数字是第0小。
这么大的数据量，你用sort()还能过吗？？？？
哈哈，用二分法

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 5e6+1;
int n,k, a[MAX];

void qsort(int begin ,int end){ 
    int temp = a[(begin+end)/2];                 //   取中间数
    int i = begin;                         //定义两个指针，从数组的两端扫
    int j = end;
    while(i <= j){
        while(a[i] < temp)  i++;       //这两个循环结束后会得到一对不满足左小右大的下标
        while(a[j] > temp)  j--;
        if(i<=j){
            swap(a[i],a[j]);
                i++;
                j--;
        }
    }  
    if(k <= j)  qsort(begin,j);        //在哪一边就在哪边查找
    else if(k >= i)  qsort(i,end);
    else{
        cout<<a[k]<<endl;
        return ；                    //此时k=j+1=i-1; 也就是（i>j）
    }
}

大家发现了吗？ 快速排序和求第k小数字的相同点就在于分治这个算法。
好了就到这里。
不会的可以给我留言哦～