• 欢迎访问hellobiancheng.com 本站包含大量编程教程、编程工具软件以及学习资源!

一背就会的算法基础模板—快速排序

编程经验 小小丁更努力 18次浏览 0个评论

一背就会的算法基础模板—快速排序

什么是快速排序?

在平均状况下,排序 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;
}
C语言网提供「C语言、C++、算法竞赛」在线课程,全部由资深研发工程师或ACM金牌大佬亲授课,更科学、全面的课程体系,以在线视频+在线评测的学习模式学习,学练同步,拒绝理论派,真正学会编程!还有奖学金等增值福利等你!

你好编程, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明一背就会的算法基础模板—快速排序
喜欢 (0)
[jinyangH@aliyun.com]
分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)