什么是快速排序？
在平均状况下，排序 n 个项目要 O ( n l o g n ) Ο(nlogn) O(nlogn) 次比较。在最坏状况下则需要 O ( n 2 ) Ο(n^2) O(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序算法模板
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);
}
模板例题
给定你一个长度为 n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n
第二行包含 n个整数（所有整数均在 1∼109范围内），表示整个数列
输出格式
输出共一行，包含 n个整数，表示排好序的数列
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
#include
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 x = q[(l+r)/2], i = l - 1, j = r + 1;
while (i < j)
{
do i++; while (q[i] < x); do j--; while (q[j] > x);
if (i < j)
{
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main()
{
scanf("%d",&n);
for (int i = 0; i < n; i++)
{
scanf("%d", &q[i]);
}
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ",q[i]);
}
printf("\n");
return 0;
}
你好编程, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明一背就会的算法基础模板—快速排序！
