快速排序——主要思想是分治

小鱼儿 2023-09-30 11:04 24阅读 0赞

### 快速排序——主要思想是分治 ###

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

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

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

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

可以使用两个指针i，j，指针i置于左边，指针j置于右边，首先将i指针一直往右移动直到遇到大于等于x的数停下来，接着就轮到指针j向左边移动，直到遇到小于等于x的数停下来，最后使用swap交换两个指针的值

![img][]

`当两个指针相遇或者穿过的时候即完整需求`

#include<iostream>
    
    using namespace std;
    
    const int N=1e6+10;
    int n;
    int q[N];
    void quick_sort(int q[],int l,int r){
        
        if(l>=r) return;
        
        int x=q[l],i=l-1,j=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);
    }
    
    
    
    int main(){
        
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&q[i]);
        
        quick_sort(q,0,n-1);
        
        for(int i=0;i<n;i++) printf("%d ",q[i]);
    }

[img]: https://img-blog.csdnimg.cn/img_convert/de62258e4395d11ff48fbb8081aaa1ab.png

发表评论取消回复

表情：

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

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

相关阅读

相关归并排序——主要思想分治

归并排序——主要思想分治 1.随机取其中的一个值，将其分为两边，最后两边分别进行递归排序 2.归并，把两个有序的序列合并成一个有序的序列 ![在这里插入图片描述][w

桃扇骨/ 2023年09月30日 11:05/ 0 赞/ 32 阅读

相关快速排序——主要思想是分治

快速排序——主要思想是分治分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

小鱼儿/ 2023年09月30日 11:04/ 0 赞/ 25 阅读

相关快速排序思想及实现

1、快速排序的思想快速排序就是给基准数据找在数组中正确位置的过程，一旦基准位置的正确位置找到，那基准位置左右两边经过同样的步骤递归也可以有序，最终整体数组有序。整

怼烎@/ 2023年06月16日 10:35/ 0 赞/ 32 阅读

相关十大排序算法-分治思想-归并排序&&快速排序(js实现)

文章目录一、分治思想二、归并排序 1.思路分析 2.排序过程演示 3.代码实现 4.复杂度分析

秒速五厘米/ 2022年11月18日 13:57/ 0 赞/ 81 阅读

相关排序算法——基于分治思想的排序

文章目录快速排序取首元素为基准随机选取基准三数取中法

怼烎@/ 2022年10月22日 15:55/ 0 赞/ 164 阅读

相关 420-分治算法-快速排序

![在这里插入图片描述][24365e4309fe4ce294b5daf50609d7d5.png] 用分治算法实现的快速排序对上面数字进行排序快速排序算法选定

喜欢ヅ旅行/ 2022年09月05日 02:00/ 0 赞/ 189 阅读

相关分治算法----快速排序

一.算法思想: 假设要对某数组进行由小->大排序 (1) 分解: 对于乱序数组a\[R\](存取范围\[0->R\],有R+1个数),取一个基准元素a\[P\](一般以第一

骑猪看日落/ 2022年07月31日 10:21/ 0 赞/ 204 阅读

相关二分思想与分治法、排序思想

二分思想与分治法、排序思想二分查找是《编程珠玑》作者很喜爱的一个话题，之前我曾经专门写了一篇博文：如何写出正确的二分查找？——利用循环不变式理解二分查找及其变体的正确性以及

爱被打了一巴掌/ 2022年07月21日 13:08/ 0 赞/ 265 阅读

相关排序算法--------快速排序(分治法 )

快速排序 1.简介 2.实现的基本思想 3.举个例子 4.java代码实现 4.1实现代码 4.2 主方法代码 5

我不是女神ヾ/ 2022年03月20日 11:56/ 0 赞/ 295 阅读

相关排序算法-快速排序（二分思想）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

青旅半醒/ 2022年02月03日 11:53/ 0 赞/ 385 阅读