【算法】快速排序与归并排序

一，快速排序

1.1模板

void quick_sort(int q[], int l, int r) {
    if (l >= r)
        return;
    int x = q[l], i = l - 1, j = r + 1;
    while (i < j) {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
        else
            break;
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
    //如果这里是i的话那么填空i-1，i。x不能取q[l]和q[(l+r)>>1]，否则会出现边界问题。
    //如果这里是j的话那么填空j，j+1。x不能取q[r]和q[(l+r+1)>>1]，否则会出现边界问题。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.2题目：第k个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1-10^9 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1<=n<=100000

1<=k<=n

输入样例

5 3
2 4 1 5 3
1
2

输出样例

3
1

AC代码

#include 

using namespace std;

int N[100010];

void quick_sort(int q[],int l,int r){
    if(l>=r)return;
    int x=q[l],i=l-1,j=r+1;
    while(ix);
        if(i>1]
    //当这里为i的时候则填i-1和i。x则不能为q[l]和q[(r+l)>>1]
}


int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i>N[i];
    quick_sort(N,0,n-1);
    cout<

int tmp[N];
void merge_sort(int q[],int l,int r){
    if(l>=r)return;
    int mid=l+r>>1;
    //递归
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    //归并的过程
    while(i<=mid&&j<=r)
        if(q[i]