// 快排模板 #include <iostream> using namespace std; const int N = 1e6 + 10; int n; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1; // 先把指针移动，再判断 // int id = rand() % (r - l) + l; // 随机取x 0~r-l -> l~r // int id = (i + j) / 2; // 取中间 // int id = (l + r) / 2; // 取中间 int id = (i + j) / 2; // 上面三种都可，这里选第二种 int x = q[id]; // 确认分界点x while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } // 递归处理左右两端 quick_sort(q, l, j); quick_sort(q, j + 1, r); //若这里用i，则上面j->i-1，j+1->i，且x=q[(l+r+1)/2]上取整，否则有边界问题 } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &q[i]); int l = 0, r = n - 1; quick_sort(q, l, r); for (int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }
求快排后的第k个数：
#include <iostream> using namespace std; const int N = 1e5 + 5; int n, k; int q[N]; void quick_sort(int q[], int l, int r)//返回值为void!!! { if (l >= r) return; // 不要忘记加 int i = l - 1, j = r + 1; int x = q[(l + r) / 2]; while (i < j) // 不要忘记 { do i++;while (q[i] < x); // 注意符号 do j--;while (q[j] > x); if (i < j) // 不要忘记 swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); } int main() { cin >> n >> k; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } quick_sort(q, 0, n - 1); printf("%d", q[k - 1]); return 0; }
