快速排序 and 第K大数

快速排序，顾名思义，它真的很快。相对于归并排序来说，它速度更快，而且不需要要辅助空间t。

其主要过程，按照分治法的三步来讲：

1、把原数组的元素分为左右两个部分，使得，左边的任意元素都 <= 右边的元素。

2、把左右两边都分别排序。

3、合并：不需要了，已经有序。

整个流程最关键的是第一步，如何在O(n)的时间内进行划分。先选择最左边的一个数为 key赋值 ，我们的目标是把小与等于 key 的放到 key 位置的左边，否则放到他的右边。我们再定义两个游标i、j，分别指向最左边和最右边。让 j 从右边扫过来，如果碰到比key 小的，那么他应该在 key 的左边，所以我们把它的值附到 i 对应的位置，原位置 i 的值在 key里。这时，那么 j 位置就相当于方 key 了。再 i 往右边扫，如果碰到 大的，那么它应该在 key 的右边，则把 位置 i 的值赋到 位置 j 。相当于key 又到了 i 的位置。也就是，每次执行完，都能保证 i 之前及 j 之后都已经达到要求了。整个过程 key 值是不变的。

可以发现它最后不用合并，只遍历了一遍，而归并遍历了两遍，它也不需要辅助空间。但是它不稳定，看选择的数，划分的时候两边规模可能相差很大。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 22222;

void quick_sort(int* a,int low,int high)//a 为原数组,范围为[low,high]
{
    if(low >= high) return ;
    //开始划分
    int i = low,j = high,key = a[low];
    while(i < j)
    {
        while(i < j && a[j] >= key) j--;
        a[i] = a[j];
        while(i < j && a[i] <= key) i++;
        a[j] = a[i];
    }
    a[i] = key;
    //划分完毕，递归求解
    quick_sort(a,low,i-1);
    quick_sort(a,j+1,high);
}

int num[MAXN];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
        scanf("%d",&num[i]);
    quick_sort(num,n-1);//范围为[0,n-1]
    for(int i = 0;i < n;i++)
        printf("%d ",num[i]);
    puts("");
    return 0;
}

第K大数

给你一个序列，问你这个序列从小到大排完序后第K大的数是多少？

最朴素的做法，就是排完序然后直接输出，复杂度O(nlogn)，但是有没有更快的方法？

看看快速排序，它的划分就正好被我们所用。划分完之后，不需要在两边都递归，只需要看k，递归一边就行了。期望意义下，时间复杂度为O(n)。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 22222;

int quick_sort(int* a,int high,int k)//a 为原数组,high]
{
    if(low == high) return a[low];
    //开始划分
    int i = low,key = a[low];
    while(i < j)
    {
        while(i < j && a[j] >= key) j--;
        a[i] = a[j];
        while(i < j && a[i] <= key) i++;
        a[j] = a[i];
    }
    a[i] = key;
    //划分完毕，递归求解
    int t = i-low+1;
    if(k == t) return a[i];
    else if(k < t) return quick_sort(a,i-1,k);
    else return quick_sort(a,high,k-t);
}

int num[MAXN];

int main()
{
    int n;
    scanf("%d",&num[i]);
    int k;
    scanf("%d",&k);
    int ans = quick_sort(num,n-1,k);//范围为[0,n-1]
    printf("%dn",ans);
    /*for(int i = 0;i < n;i++)
        printf("%d ",num[i]);
    puts("");*/
    return 0;
}

/*
11
6 7 1 2 3 4 1 3 11 0 99

*/