快速排序

void quick_sort(int q[], int l, int r)
{
	if (l >= r)
		return;
	int i = l - 1, j = r + 1, x = q[l + r >> 1];
	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);
}

快速选择

每次判断目标点在左边还是右边，如果在左边,下次就只递归左边。

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int N = 1e6 + 9;
int a[N];
int quick(int l, int r, int k)
{
	if (l == r)
		return a[l];
	int x = a[l], i = l - 1, j = r + 1;
	while (i < j)
	{
		
		while (a[++i] < x);
		
		while (a[--j] > x);
		if (i < j)
			swap(a[i], a[j]);
	}
	int sl = j - l + 1;
	if (sl >= k)
		return quick(l, j, k);
	else
		return quick(j + 1, r, k - sl);
}
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	cout << quick(0, n - 1, k) << endl;
	return 0;
}

归并排序

void merge_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
		if (q[i] <= q[j]) tem[k++] = q[i++];
		else tem[k++] = q[j++];
	while (i <= mid) tem[k++] = q[i++];
	while (j <= r) tem[k++] = q[j++];
	for (int i = l,j =0; i <= r; i++, j++) q[i] = tem[j];
}