首页 > 其他分享 >快速排序

快速排序

时间:2023-10-05 20:33:58浏览次数:38  
标签:sort 数列 int 算法 序列 排序 快速

一、算法描述

快速排序算法是对冒泡排序算法的一种改进算法,在当前所有内部排序算法中,快速排序算法被认为是最好的排序算法之一。

快速排序的基本思想: 通过一趟排序将待排序的序列分割为左右两个子序列,左边的子序列中所有数据都比右边子序列中的数据小,然后对左右两个子序列继续进行排序,直到整个序列有序。

思路如下:

  1. 选择分界点,int x = q[l], q[r], q[(l + r) >> 1]
  2. 调整区间,使得左区间所有的数都≤x ,右区间所有的数都≥x
  3. 递归调整所得的两个区间
  • 快排的思想比较重要,基于分治,虽然竞赛或者其他的写代码都是直接用sort,但是会手写快排还是很重要的的。
  • 快排中的下标问题很多,比如q[l]不能用iq[r]不能用j,所以背模板很重要。
  • 建议用一组数据来模拟一下快排的实现过程,例如3 1 4 2 3 5

二、题目描述

给定你一个长度为 \(n\) 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 \(n\)。

第二行包含 \(n\) 个整数(所有整数均在 \(1\)~\(10^9\) 范围内),表示整个数列。

输出格式

输出共一行,包含 \(n\) 个整数,表示排好序的数列。

数据范围

\(1 ≤ n ≤ 100000\)

输入样例:

5
3 1 2 4 5 

输出样例:

1 2 3 4 5 

三、原题链接

AcWing785.快速排序

四、源代码

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];

void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;
    
    int x = a[(l + r) >> 1], i = l - 1, j = 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]);
    }
    
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

int main()
{
    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;
}

标签:sort,数列,int,算法,序列,排序,快速
From: https://www.cnblogs.com/grave-master/p/17743832.html

相关文章

  • AcWing_1_1_785_快速排序
    一、题目描述给定你一个长度为n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行,第一行包含整数n。第二行包含n个整数(所有整数均在\(1∼10^9\)范围内),表示整个数列。输出格式输出共一行,包含n个整数,......
  • 合并区间(区间排序,vector的动态扩容的应用)
    以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。示例1:输入:intervals=[[1,3],[2,6],[8,10],[15,18]]输出:[[1,6],[8,10],[15,18]]解释:区间[1,3......
  • 根据某个关键字的指定顺序,重新对数据源快速排序!
    1职场实例小伙伴们大家好,今天我们来继续重温并学习一个Excel使用过程中最基础的技巧之一:如何根据某个关键字指定的顺序,重新对数据源快速排序?这个问题算是判断掌握Excel是否熟练的一个重要指标了,下面我们就来看一下具体的问题场景。如下图所示:A1:B6单元格区域为数据源区域,为一份水果......
  • 【基础算法】排序算法 —— 插入排序
    一、算法原理插入排序将数组分为已排序区间和未排序区间,初始已排序区间只有数组第1个元素,未排序区间从下标1开始到数组末尾。每次取未排序区间的第1个元素,将它插入已排序区间的合适位置,并保证已排序区间一直有序。重复这个过程,直到未排序区间为空,算法结束。给有序数组(已排序区......
  • 【基础算法】排序算法 —— 选择排序
    一、算法原理选择排序将数组分为已排序区间和未排序区间,每次选择未排序区间的最小元素,将它放到已排序区间末尾。一次选择会让一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序。 示例:使用选择排序对数组arr=[4,5,6,3,2,1]从小到大排序。第1次选择:第2次选择:......
  • 【基础算法】排序算法 —— 冒泡排序
    一、算法原理冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,如果不满足大小关系要求,就进行交换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序。 示例:使用冒泡排序对数组arr=[4,5,6,3,2,1]从小到大排序。第1次......
  • Centos 快速查看占用资源最多的进程
    1、查看占用内存最多的十个进程psaux|head-1;psaux|grep-vPID|sort-rn-k+4|head 2、查看占用cpu最多的十个进程psaux|head-1;psaux|grep-vPID|sort-rn-k+3|head ————————————————版权声明:本文为CSDN博主「zhangjunli」的原创文......
  • MySQL学习(3)B+树索引是如何快速查询的
    前言我们已经知道在磁盘中,有很多索引页,这些页并非在物理结构上相连接,而是通过双向链表关联。如果要查找一条数据,需要通过页目录中的槽,通过二分法定位到分组再进行遍历查找。比如下面这样:SELECT[查询列表]FROM表名WHERE条件; 假设表中只有一个页,在查找记录时,可以根据搜......
  • 【基础算法】排序算法
    一、排序算法简介排序是对批量数据按照一定的顺序进行排列的操作。1.1学习排序算法的要点算法原理、代码实现、评价算法优劣。1.2评价排序算法的优劣排序算法的优劣可以从以下3个方面进行评价:时间性能:最好、最坏、平均时间复杂度;内存占用:是否原地排序,原地排序算法,......
  • eslint airbnb React18+typescript 依赖循环、import自动排序分组
    eslint终极规范爱彼迎eslint-config-airbnb请先阅读完下以下链接在来配置代码规范之什么是eslint,为什么要使用eslinteslint的配置项过多,针对js、ts、vue、jsx、tsx等等不同的规则,小公司或者个人项目可以使用成熟的eslint社区规范,如airbnb、standard、goole等。这里我们介绍......