【洛谷 P1177】【模板】快速排序 题解(快速排序+数组索引)

简介: **快速排序模板题目**,要求使用快排算法对输入的整数序列进行排序。输入包含正整数N和N个整数,输出排序后的序列。20%的数据N≤10^3,所有数据N≤10^5。代码中提供了一种实现,包括读取输入、定义partition函数划分数组、递归调用quickSort及主函数执行排序和输出。注意C++选手避免使用STL的`sort`。

【模板】快速排序

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料,掌握后独立完成。(C++ 选手请不要试图使用 STL,虽然你可以使用 sort 一遍过,但是你并没有掌握快速排序算法的精髓。)

输入格式

第 $1$ 行为一个正整数 $N$,第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$,为你需要进行排序的数,数据保证了 $a_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出,数之间空格隔开,行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 $20\%$ 的数据,有 $N\leq 10^3$;

对于 $100\%$ 的数据,有 $N\leq 10^5$。

思路

快速排序。数据过大,需要打开O2优化。

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

void read(int &x){
   
    x = 0;
    char ch;
    while (('0' > ch || '9' < ch))
    {
   
        ch = getchar();
    }
    while (!('0' > ch || '9' < ch))
    {
   
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int partition(int a[], int low, int high)
{
   
    int i = low, j = high, pivot = a[low];
    while (i < j)
    {
   
        while (i < j && a[j] > pivot) // 向左扫描
        {
   
            j--;
        }
        while (i < j && a[i] <= pivot) // 向右扫描
        {
   
            i++;
        }
        if (i < j)
        {
   
            swap(a[i++], a[j--]);
        }
    }
    if (a[i] > pivot)
    {
   
        swap(a[i - 1], a[low]);
        return i - 1;
    }
    else
    {
   
        swap(a[i], a[low]);
        return i;
    }
}

void quickSort(int a[], int low, int high)
{
   
    if (low < high)
    {
   
        int mid = partition(a, low, high);
        quickSort(a, low, mid - 1);
        quickSort(a, mid + 1, high);
    }
}

int n;

int main()
{
   
    read(n);
    int *arr = new int[n];
    for (int i = 0; i < n; i++)
    {
   
        read(arr[i]);
    }
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
   
        cout << arr[i] << " ";
    }
    delete[] arr;
    return 0;
}
目录
相关文章
|
算法 Java 调度
操作系统之进程调度——优先权法和轮转法(附上样例讲解)
多道程序设计中,经常是若干个进程同时处于就绪状态,必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。
1081 0
操作系统之进程调度——优先权法和轮转法(附上样例讲解)
|
SQL 缓存 Oracle
一文教会你如何在SpringBoot项目里集成Hibernate
一文教会你如何在SpringBoot项目里集成Hibernate
1347 1
|
存储
【洛谷 P1255】数楼梯 题解(递归+记忆化搜索+高精度)
这是一个使用动态规划解决的“数楼梯”问题。给定楼梯数`N`,求不同上楼方式的数量。程序通过递归函数`f()`计算,其中`f(x) = f(x - 1) + f(x - 2)`,初始条件`f(1) = 1`,`f(2) = 2`。考虑到数据规模可能很大,使用了高精度加法运算。样例输入`4`,输出`5`。代码中定义了一个存储中间结果的向量`mem`,并提供了一个用于显示高精度数的`printv()`函数。
258 0
|
11月前
|
存储 Python
提升工作效率:获取任意月份的所有工作日
本文介绍了如何使用 Python 编写一个简单程序,以获取任意月份的所有工作日。通过 `datetime` 和 `calendar` 模块,程序能够准确地识别出每个月的周一至周五,帮助用户高效管理时间和任务。
318 6
|
机器学习/深度学习 算法
概率分布深度解析:PMF、PDF和CDF的技术指南
本文将深入探讨概率分布,详细阐述概率质量函数(PMF)、概率密度函数(PDF)和累积分布函数(CDF)这些核心概念,并通过实际示例进行说明。
1013 15
概率分布深度解析:PMF、PDF和CDF的技术指南
|
11月前
|
机器学习/深度学习 人工智能 数据处理
【AI系统】NV Switch 深度解析
英伟达的NVSwitch技术是高性能计算领域的重大突破,旨在解决多GPU系统中数据传输的瓶颈问题。通过提供比PCIe高10倍的带宽,NVLink实现了GPU间的直接数据交换,减少了延迟,提高了吞吐量。NVSwitch则进一步推动了这一技术的发展,支持更多NVLink接口,实现无阻塞的全互联GPU系统,极大提升了数据交换效率和系统灵活性,为构建强大的计算集群奠定了基础。
906 3
|
存储 负载均衡 算法
深入理解操作系统的进程调度
【6月更文挑战第20天】本文将探讨操作系统中的进程调度,包括其定义、重要性以及常见的调度算法。我们将通过具体的例子和代码片段来深入理解进程调度的工作原理和实现方式。最后,我们将讨论进程调度在现代操作系统中的应用和挑战。
|
边缘计算 Cloud Native 物联网
探索数据库技术的未来:前沿发展与应用场景
一、引言 数据库技术作为信息时代的基石,承载着存储、管理和分析海量数据的重要任务
|
存储 数据采集 缓存
【运维知识进阶篇】Zabbix5.0稳定版详解9(Zabbix优化:高并发对MySQL进行拆分、Zabbix-agent主动上报模式、使用proxy代理模式、系统自带监控项优化、进程优化、缓存优化)
【运维知识进阶篇】Zabbix5.0稳定版详解9(Zabbix优化:高并发对MySQL进行拆分、Zabbix-agent主动上报模式、使用proxy代理模式、系统自带监控项优化、进程优化、缓存优化)
1427 0
|
SQL HIVE
【Hive SQL 每日一题】统计用户连续下单的日期区间
该SQL代码用于统计用户连续下单的日期区间。首先按`user_id`和`order_date`分组并去除重复,然后使用`row_number()`标记行号,并通过`date_sub`与行号计算潜在的连续日期。接着按用户ID和计算后的日期分组,排除连续订单数少于2的情况,最后提取连续下单的起始和结束日期。输出结果展示了用户连续下单的日期范围。
416 0