题目一

解题思路

快排思路

1. 首先设定一个分界值(基准值)，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3. 左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

PS：快排算法的边界处理非常繁琐， 建议直接背一个快排模板直接用

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;
int a[N];void quick_sort(int a[], int l, int r)
{if (l >= r){return ;}int i = l, j = r;int pivot = a[(l + r) >> 1];while (i <= j){while (a[i] < pivot){i ++;}while (a[j] > pivot){j --;}if (i <= j){swap(a[i], a[j]);i ++;j --;}}quick_sort(a, l, j);quick_sort(a, i, r);
}int main()
{int n;cin >> 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]);}return 0;
}

题目二

解题思路

与题一相同

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;
int a[N];void quick_sort(int l, int r, int a[])
{if (l >= r){return ;}int i = l, j = r, pivot = a[(l + r) >> 1];while (i <= j){while (a[i] < pivot){i ++;}while (a[j] > pivot){j --;}if (i <= j){swap(a[i], a[j]);i ++;j --;}}quick_sort(l, j, a);quick_sort(i, r, a);
}int main()
{int n, k;cin >> n >> k;for (int i = 0; i < n; i ++ ){scanf("%d", &a[i]);}quick_sort(0, n - 1, a);printf("%d", a[k - 1]);return 0;
}