快速排序 AcWing 785. 快速排序

野性酷女 2023-09-28 11:07 123阅读 0赞

## 快速排序 AcWing 785. 快速排序 ##

### 原题链接 ###

[AcWing 785. 快速排序][AcWing 785.]

### 算法标签 ###

快速排序

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    const int N = 100005;
    int a[N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n=read();
    	rep(i, 0, n){
    	    a[i]=read();
    	}
    	sort(a, a+n);
    	rep(i, 0, n){
    	    printf("%lld ", a[i]);
    	}
    	return 0;
    }

### 手写sort代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    const int N = 100005;
    int a[N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    void q_sort(int a[], int l, int r){
    	// 递归的终止情况
        if(l>=r){
            return;
        }
        // 第一步：分成子问题
        int i=l-1, j=r+1, x=a[l+r>>1];
        while(i<j){
            do{
                ++i;
            }while(a[i]<x);
            do{
                --j;
            }while(a[j]>x);
            if(i<j){
                swap(a[i], a[j]);
            }
        }
        // 第二步：递归处理子问题
        q_sort(a, l, j);
        q_sort(a, j+1, r);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n=read();
    	rep(i, 0, n){
    	    a[i]=read();
    	}
    	q_sort(a, 0, n-1);
    	rep(i, 0, n){
    	    printf("%lld ", a[i]);
    	}
    	return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 785.]: https://www.acwing.com/problem/content/787/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png

发表评论取消回复

表情：

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

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

相关阅读

相关 785. 快速排序

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

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

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

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

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

相关【排序】快速排序

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

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

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

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

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

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

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

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

相关排序——快速排序

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

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

相关快速排序

//快速排序相比于冒泡、插入排序等有更大的优势，所以也是必须熟练掌握的。 include <stdio.h> void quick_sort

野性酷女/ 2022年07月15日 06:23/ 0 赞/ 189 阅读

相关快速排序

相信算法对于许多开发人员来说都是一大难点，之所以难，就像设计模式一样，许多人在阅读之后，没有很好地理解，也不愿意动手上机操作，只停留在理论的学习上面，随着时间推移就慢慢淡忘。

旧城等待，/ 2022年06月08日 14:05/ 0 赞/ 192 阅读

相关快速排序

学习之后，自己练习手写一下排序算法，加深印象原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行

╰+攻爆jí腚メ/ 2022年05月28日 04:39/ 0 赞/ 179 阅读

相关排序——快速排序

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

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