785. 快速排序

谁借莪１个温暖的怀抱￠ 2024-05-01 16:06 67阅读 0赞

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

输入格式

> 输入共两行，第一行包含整数 nn。
> 
> 第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

> 输出共一行，包含 nn 个整数，表示排好序的数列。

数据范围

> 1≤n≤1000001≤n≤100000

输入样例：

5
    3 1 2 4 5

输出样例：

1 2 3 4 5

#include<iostream>
    #include<algorithm>
    using namespace std;
    void quick_sort(int a[],int l,int r)
    {
    	if(l>=r)return ;
    	int i=l-1,j=r+1,t=a[l+r>>1];
    	while(i<j)
    	{
    		do ++i;while(a[i]<t);
    		do --j;while(a[j]>t);
    		if(i<j)swap(a[i],a[j]);
    	}
    	quick_sort(a,l,j);
    	quick_sort(a,j+1,r);
    }
    int main()
    {
    	int n,a[100005];
    	cin>>n;
    	for(int i=0;i<n;i++)
    	cin>>a[i];
    	quick_sort(a,0,n-1);
    	for(int i=0;i<n;i++)
    	cout<<a[i]<<" ";
    	return 0;
    }

快排模板：

基准数选取中点位置的数，减少循环次数，因为数组可能有一定的有序性  
i与j为哨兵 i从左向右找大于基准数的数  
j从右向左找小于基准数的数  
如果哨兵没有相遇 交换所指的值  
哨兵相遇 循环结束

void quick_sort(int a[],int l,int r)
    {
    	if(l>=r)return ;
    	int i=l-1,j=r+1,t=a[l+r>>1];
    	while(i<j)
    	{
    		do ++i;while(a[i]<t);
    		do --j;while(a[j]>t);
    		if(i<j)swap(a[i],a[j]);
    	}
    	quick_sort(a,l,j);
    	quick_sort(a,j+1,r);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，67人围观）

还没有评论，来说两句吧...

相关阅读

相关 785. 快速排序

给定你一个长度为nn的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行，第一行包含整数nn。第二行包含nn个整数（...

谁借莪１个温暖的怀抱￠/ 2024年05月01日 16:06/ 0 赞/ 68 阅读

相关 785. 判断二分图

存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph\[u\] 是一个节点数组

浅浅的花香味﹌/ 2024年03月27日 08:44/ 0 赞/ 63 阅读

相关快速排序_详解快速排序算法

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对[冒泡排序][Link 1]算法的一种改进。快速排序的排序流程快速排序算法通

快来打我*/ 2023年09月28日 22:53/ 0 赞/ 130 阅读

相关快速排序 AcWing 785. 快速排序

快速排序 AcWing 785. 快速排序原题链接 [AcWing 785. 快速排序][AcWing 785.] 算法标签快速排序代码

野性酷女/ 2023年09月28日 11:07/ 0 赞/ 141 阅读

相关 785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合

╰+攻爆jí腚メ/ 2023年02月26日 14:27/ 0 赞/ 1 阅读

相关【排序】快速排序

快速排序 [快速排序][Link 1]和冒泡排序都是是交换排序中的一种。基本思想 1，在数列中找准一个基准点`pivot`。 2，将

àì夳堔傛蜴生んèń/ 2022年12月13日 04:41/ 0 赞/ 210 阅读

相关 python快速排序_Python快速排序

![9132f6c40cfac296f5705ed5ab1e73dc.png][] python快速排序 Here you get python quick sort pr

电玩女神/ 2022年12月07日 13:29/ 0 赞/ 306 阅读

相关 python快速排序排序_python快速排序

import random def rand(n): for i in range(n): yield random.randint(0,1000) \创建一个随机数列

我会带着你远行/ 2022年10月25日 15:26/ 0 赞/ 306 阅读

相关排序——快速排序

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASeKAmG0gSmll_si

￡神魔★判官ぃ/ 2022年09月10日 08:18/ 0 赞/ 261 阅读

相关排序——快速排序

排序——快速排序 include <iostream> using namespace std; //快速排序实现 include

朴灿烈づ我的快乐病毒、/ 2022年05月21日 12:05/ 0 赞/ 305 阅读