快速排序

给定你一个长度为 n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

image-20221120203230081

前摘提要

首先我先来介绍一下快速排序算法，它被誉为最快排序算法，可以快到nlogn级别，而且在c++中已经有了相关的函数sort(),所以在算法竞赛中它的模板其实也没有那么重要(毕竟算法竞赛是要赶时间的嘛，太慢了题都搞不定)，但是这里还是要介绍一下这个算法的思想。

算法思想

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;

	int x = q[l]; int i = l - 1, j = 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);
}

它主要是采用了双指针的思想来解题的，也就是说我们创建两个指针(其实不是真要创建两个指针，实际上是两个变量l,r) 一个呢，从左到右来进行，一个从右到左来进行,我们再设立一个中间量，就第三个数了

我们以示例来讲，假设l在左边，r在右边，我们要从小到大来排序，先看l，它指向了第一个数3，3比2大，好l停下来，让r走，r走啊走，走到第四位时大于2，走到第三位时相等了，此时呢我们发现l所指的数3是大于r所指的数的，我们交换一下l和r的数字位置，此时排序变成了 2 1 3 4 5，我们再进行一次快排

新的循环

此时的排序是2 1 3，我们还是取中间的量1，l所指的数刚好比1大，停下来，r指的数比1小，再退一个，r现在指的数就是1了，现在l左边的数是严格小于的，r右边的数是严格大于的，交换两数后，变成1 2 3了，我们再进入一次快排

最后的循环

我们发现两个循环1 2 3和4 5是严格从小到大的，这时候我们就可以返回去输出了，这样的算法复杂度是最快的

输出答案和程序书写建议

下面是定义变量，函数应用和输出变量的写法，谢谢观看@*@！

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N = 1e6 + 10;
int q[N], n;
int main()
{
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf_s("%d", &q[i]);
	}

	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", q[i]);
	}
	return 0;
}

引入

—acwing算法基础课 (yxc主讲)