快速排序模板

叁歲伎倆 2023-09-30 11:06 7阅读 0赞

1.确定分界点 q\[l\] q\[(r+l)/2\] q\[r\] 随机选一个，选择好了之后将区间分为两部分

2.调整区间，将小于等于x的置于左边，大于等于x的置于右边，这里需要注意，如果等于x，放在左边或者右边都可以

3.使用递归处理左右两段

可以使用两个指针i，j，指针i置于左边，指针j置于右边，首先将i指针一直往右移动直到遇到大于等于x的数停下来，接着就轮到指针j向左边移动，直到遇到小于等于x的数停下来，最后使用swap交换两个指针的值  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]

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);
    }

来源：【Acwin】

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7e08334bbe3b44a3ba8ef8f840689281.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiD5a-75YyX6YeM,size_20,color_FFFFFF,t_70,g_se,x_16

发表评论取消回复

表情：

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

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

相关阅读

相关一、基础算法1：快速排序模板题+算法模板（快速排序，快速找出第k小的数）

文章目录算法模板快速排序算法模板查找第k个数算法模板模板题快速排序原题链接

小咪咪/ 2023年10月08日 20:47/ 0 赞/ 51 阅读

相关快速理解快速排序（附java模板）

前言：很多人认为排序直接用sort函数它不香吗，emmm确实平时刷题如果需要先进行排序我们基本都会直接使用sort函数（不太了解sort的可以自行上网搜索）。但其实排序算法

爱被打了一巴掌/ 2023年10月04日 15:41/ 0 赞/ 14 阅读

相关快速排序模板

1.确定分界点 q\[l\] q\[(r+l)/2\] q\[r\] 随机选一个，选择好了之后将区间分为两部分 2.调整区间，将小于等于x的置于左边，大于等于x的置于右边，这

叁歲伎倆/ 2023年09月30日 11:06/ 0 赞/ 8 阅读

相关快速排序模板（循环+递归）

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部

朴灿烈づ我的快乐病毒、/ 2023年02月16日 05:59/ 0 赞/ 24 阅读

相关【模板】快速排序

[题目][Link 1] include <bits/stdc++.h> using namespace std; int a[100010];

左手的ㄟ右手/ 2022年11月14日 10:20/ 0 赞/ 161 阅读

相关【模板】快速排序与归并排序——Template，QuickSort&MergeSort

快速排序 include<iostream> using namespace std; int n,a[1000001]; void qsor

秒速五厘米/ 2022年11月12日 02:51/ 0 赞/ 235 阅读

相关快速排序模板

其实不太想写，因为意义不大，真正比赛的时候，没有人会去用，直接sort就行快速排序，平均 O ( n l o g n ) O(nlogn) O(nlogn)，最坏

男娘i/ 2022年08月29日 13:48/ 0 赞/ 147 阅读

相关 C++模板快速排序和Stooge排序

快速排序和Stooge排序快速排序简介快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-li

柔光的暖阳◎/ 2022年07月28日 01:45/ 0 赞/ 179 阅读

相关洛谷P1177 【模板】快速排序

题目描述利用快速排序算法将读入的N个数从小到大排序后输出。快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。

Myth丶恋晨/ 2022年05月31日 08:49/ 0 赞/ 253 阅读

相关快速排序模板整理

快速排序 1.思想快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小，

Love The Way You Lie/ 2021年07月24日 21:03/ 0 赞/ 422 阅读