1.c++的scanf的效率比cin效率更改
2.java的bufferread比scanner快10-20倍

报告时间超过,不明白为什么。 

  1. # include <iostream>
  3. int partition(int a[], int l, int r) {
  4.     int temp = a[l];
  5.     a[l] = a[(l + r) / 2];
  6.     a[(l + r) / 2] = temp;
  8.     temp = a[l];
  9.     while (l < r) {
  10.         while (l < r && a[r] >= temp) r--;
  11.         a[l] = a[r];
  12.         while (l < r && a[l] <= temp) l++;
  13.         a[r] = a[l];
  14.     }
  15.     a[l] = temp;
  16.     return l;
  17. };
  19. void quick_sort(int a[], int l, int r) {
  20.     if (l < r) {
  21.         int i = partition(a, l, r);
  22.         quick_sort(a, l, i - 1);
  23.         quick_sort(a, i + 1, r);
  24.     }
  25. }
  27. const int N = 1e5 + 10;
  28. int n;
  29. int a[N];
  31. int main() {
  32.     scanf("%d", &n);
  33.     for (int i = 0; i < n; ++i) {
  34.         scanf("%d", &a[i]);
  35.     }
  36.     quick_sort(a, 0, n - 1);
  37.     for (int i = 0; i < n; ++i) {
  38.         printf("%d ", a[i]);
  39.     }
  40. }

OJ中的状态术语：
AC (Accepted= 答案正确)，WA (Wrong Answer=答案错误)，
TLE(Time Limit Exceeded =运行超时/时间超限)，
CE (Compile Error=编译错误)，
RE(Runtime Error =运行时出错)，
MLE(Memory Limit Exceeded =内存超限)，
PE (Presentation Error=格式错误)

一：快速排序的板子

  • 算法理解：这里的排序算法和之前学习的马桶快速排序明显不同，因为，每一次的循环不是选定一个元素，本质是让选择两个区间，左边的区间小于等于选定的值，右边的区间大于等于选定的值，这一点非常关键。之前学习的马桶快速排序在上面，放在acwing中校验的时候，总是出现TLE的错误。
  • 在acwing中加强了数据校验，当数据基本有序的时候，你选择最左或者最右端的时候，算法会退化到最差的情况，第一分成一个元素一个区间，n-1个元素一个区间，依次类推，每次我都分出一个元素，没轮次的计算量都是n，达到n^2级别。 ```cpp

    include

using namespace std;

const int N = 1e5 + 10; // ACM那块的的习惯还是什么，反正保留这样的习惯刷算法 int n; int a[N]; void quick_sort(int a[], int l, int r) { if (l >= r) return; // 这里可以是l == r,只不过是个人习惯的问题 int i = l - 1, j = r + 1, x = a[l + r >> 1]; // 这里有个错误犯了多遍， l + r >> 1 <==> (l+r)/2优先级 // 如果你写成 i = l, j = r后面的程序就得修改，一旦修改以后，就会出现边界问题已经验证 while (i < j) { while (a[++i] < x); // 有的语言并不支持do while，所以这里本质由do while改进而来 while (a[—j] > x); // 这两行为什么不能等于，等于的时候，当你选定的界定值恰巧是最大的，会发生数组越界 1 5 3，选定5，以后，第一个while会一直向后执行，知道数组下表发生越界访问 if (i < j) swap(a[i], a[j]); // 对于i 和 j 跳出循环的情况可能存在 i == j和 i > j的情况 }

  1. quick_sort(a, l, j); // 这里选择的一定注意边界问题，这里选择j的时候，上面的x定位的时候，不能定位到r的位置，例如，1，2的时候，如果你选择元素的时候，选的是r发生死循环，TLE错误
  2. quick_sort(a, j + 1, r);// 上面的l + r >> 1就是为了避免这个问题，就是区间分割的时候，出现了一个区间是2的时候，也是选择左边的元素，避免出现死循环的问题。

}

int main() { scanf(“%d”, &n); for (int i = 0;i < n; i++) { scanf(“%d”, &a[i]); } quick_sort(a, 0, n-1); for (int i = 0; i < n; i++) { printf(“%d “, a[i]); } }


- ![image.png](https://cdn.nlark.com/yuque/0/2021/png/312760/1619336784448-e4c85435-7703-4da8-b535-bc3a1c23cd43.png#height=25&id=huJzC&margin=%5Bobject%20Object%5D&name=image.png&originHeight=50&originWidth=204&originalType=binary&size=2051&status=done&style=none&width=102)这里的a[++i] > x，a[--j] < x，把符号变成相反的时候，就是从大到小的逆序排序
<a name="JSA2C"></a>
## 二：快速排序应用 -- 第k个数（排序后的）
<a name="tEzFl"></a>
### 分析：

- 运用快速选择算法，快速排序完全的时间复杂度到了 n*logn的级别
- 基本原理：每次分成两个区间，第一区间小于等于枢轴值，第二区间大于等于枢轴值，也就是说前面那个区间是当前整个区间最小的前 j - l + 1个数。

具体过程，每轮的quick_sort分成的两个区间，如果每轮的第k个数是不断变化的，每轮需要判断 K和前一个区间的大小，小于的话，后面的区间就不用进行函数的嵌套，时间复杂度的分析  n + n / 2 + n / 4 + n / 8....就是一个等比数列，肯定小于 2n,所以时间复杂度在n的级别

<a name="kkAoh"></a>
### 具体代码：
```cpp
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, k;
int a[N];

int quick_sort(int l ,int r, int k) {
    if (l == r) return a[l];
    int i = l - 1, j = r + 1,x = a[l + r >> 1];
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    int temp = j - l + 1;
    if (k <= temp) return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - temp);
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }

    cout << quick_sort(0, n - 1, k);
}