这两天回头大复习，做了一下洛谷的一道题

知识点是手写快排加分治

P1923 【深基9.例4】求第 k 小的数

自己写的代码交了20篇整才照着题解写出来篇AC的（太屑了

然而还有好多问题没有闹明白

暂且记录一下

 1 //AC代码 
 2 //感觉此题是道玄学题 
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5 int n,k,a[5000005];
 6 void qsort(int l,int r){
 7 //    if(l>=r)return ;
 8 //加上会输出3，正确结果应为2，原因不明 
 9     int i=l,j=r,x=a[(l+r)/2];
10     while(i<=j){//=保证i>j 
11         while(a[i]<x)i++;
12         while(a[j]>x)j--;
13         if(i<=j){
14             swap(a[i],a[j]);
15             i++;
16             j--;
17         }
18     }
19     //没有以下代码 60分
20     //分治，经过while以后，l<=j<i<=r(l==r除外 
21     if(k<=j)qsort(l,j);//k在左区间，只关注左边 
22     if(i<=k)qsort(i,r);//右区间 
23     else{//k在j和i中间（j和i中间一定只有一个数，l==r除外 
24         printf("%d",a[j+1]);
25         exit(0);
26         //不加exit会输出2 3，正确结果应仅有2
27         //exit（0）表示程序正常结束； 
28     }
29 }
30 int main(){
31     scanf("%d%d",&n,&k);
32     for(int i=0;i<n;i++){
33         scanf("%d",&a[i]);
34     }
35     qsort(0,n-1);
36     return 0;
37 }
38 
39 
40 //错误代码
41 //#include <bits/stdc++.h>
42 //using namespace std;
43 //int n,k;
44 //const int maxn=5e6+5;
45 //int a[maxn];
46 //void qsort(int l,int r){
47 //    if(l>=r)return ;
48 //    int i=l-1,j=r+1,x=a[(l+r)/2];
49 //    while(i<=j){
50 //        do i++;while(a[i]<x);
51 //        do j--;while(a[j]>x);
52 //        //a[j]>=x会运行错误，原因不明 
53 //        if(i<=j)swap(a[i],a[j]);
54 //    }
55 ////    qsort(l,j);
56 ////    qsort(j+1,r);
57 //    //如果把j改成i会全部MLE，原因不明 
58 //    //如果没有以下优化会TLE两个点
59 //    //！！！
60 ////    if(k<j) qsort(l,j+1);
61 //    //如果在数组左边，只遍历左边部分 
62 //    //！！！qsort(l,j)不输出，但是 qsort(l,j+1)就OK 
63 //    
64 ////    else if(k>i) qsort(i+1,r);
65 //
66 ////    else if(k>j) qsort(j+1,r);
67 //    //如果在数组右边，只遍历右边部分 
68 //    //bug同上 
69 ////    else {
70 //    //如果在中间，直接输出即可 
71 ////        printf("%d",a[j]); 
72 ////    }
73 //    
74 //    
75 //    //优化后1AC，2WA，2MLE？？？ 
76 //    if(k>=i)qsort(i+1,r);
77 //    else if(k<=j)qsort(l,j-1);
78 //    else{
79 //        printf("%d",a[j]);
80 //    }
81 //}
82 //int main(){
83 //    scanf("%d%d",&n,&k);
84 //    for(int i=0;i<n;i++)scanf("%d",&a[i]);
85 //    qsort(0,n-1);
86 ////    printf("%d ",a[k]);
87 //    return 0;
88 //}