快速排序及运用

1.快速排序题目要求

给定你一个长度为 \(n\) 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 \(n\)。 第二行包含 \(n\) 个整数（所有整数均在1~10^9范围内），表示整个数列。

输出格式 输出共一行，包含 \(n\) 个整数，表示排好序的数列。

数据范围
1 ≤ n ≤ 100000
输入样例：

5 
3 1 2 4 5 

输出样例：

1 2 3 4 5

算法的基本思想和步骤：
该算法主要运用了分治的思想，通过递归的方法进行大小排序。 第一步：确定分界点x。这里可以选择左右边界数或者是中间数。 第二步：调整区间。通过指针的移动以及对应数的交换,实现x的左边的数都小于等于x, x的右边的数都大于等于x。 第三步：递归处理左右两段。

题目关键点：
本题的关键点在于调整区间。采用从前向后和从后向前的双向遍历的方法进行排序，当遇到不符合条件的数据时停下来，进行指针所指向位置的比较，如果没有相遇，则进行两数交换。然后继续遍历，直至指针相遇。在选择递归的边界点时，也应当注意与分界点相对应。

程序代码：

#pragma
#include <iostream>

const int N = 1e6;
int q[N];

void quick_sort(int l, int r, int q[])
{
	if (l >= r) return;
	//这里注意思考边界，用l, 下面就是j和j+1, 用r下面就是i-1,和i
	// 用q[l + r  + 1 >> 1], 边界就用i - 1, i
	// 用q[l + r >> 1]，边界就用j, j + 1
	int i = l - 1, j = r + 1, x = q[l]; 

	while (i < j)
	{
		while (q[++i] < x);
		while (q[--j] > x);

		if (i < j) std::swap(q[i], q[j]);
	}

	quick_sort(l, j, q);
	quick_sort(j + 1, r, q);
}

void quick_sort()
{
	int n;
	std::cin >> n;
	for (int i = 0; i < n; ++i)
		std::cin >> q[i];

	quick_sort(0, n - 1, q);

	for (int i = 0; i < n; ++i)
		std::cout << q[i] << " ";

	std::cout << std::endl;
}

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

输出样例：

3

程序代码：

每次递归时只扫目标数所在的区间，降低时间复杂度。

#pragma once
#include <iostream>

const int N = 1000010;

int q[N];

int n, k;

int kth_number(int l, int r, int q[], int k)
{
	if (l == r) return q[l]; //当区间中只有一个数字时，那么这个数字就是答案

	int i = l - 1, j = r + 1;
	int x = q[l];

	while (i < j)
	{
		while (q[++i] < x);
		while (q[--j] > x);

		if (i < j) std::swap(q[i], q[j]);
	}

	int left_number = j - l + 1; //左半边数组元素的数量
	if (left_number >= k) return kth_number(l, j, q, k); //如果k小于等于左边，说明在左边
	else return kth_number(j + 1, r, q, k - left_number); //否则说明在右边，更新一下k
}

void kth_number()
{
	std::cin >> n >> k;

	for (int i = 0; i < n; ++i) std::cin >> q[i];

	std::cout << kth_number(0, n - 1, q, k);
}