快速排序

Myth丶恋晨 2021-06-22 15:36 394阅读 0赞

最好记一个模板不然有时会出现边界问题，如果选取ans[l]为分界点时，
    区间就不能划分为（l，i-1）（i，r）例如0,2就会无限循环下去，
    同理如果选取ans[r]为分界点时不能划分区间为（l，j）（j+1，r）
    最好选取ans[(l+r)/2]不容易发生边界问题

#include <iostream>`
    
    using namespace std;
    const int maxn=1e5+10;
    int ans[maxn];

void quicksort(int ans[],int l,int r){ 
    	int mid,x,i,j;//两个指针，分别标记左边和右边边界
    
    	mid=(l+r)/2;
    	x=ans[mid];
    	i=l-1;//i指向l的左边
    	j=r+1;//j指向r的右边因为后面进dowhile行循环的时候会先进行i++,j--
    	if(l>=r)
    	{ 
    		return ;//当只有一个的时候退出
    	}
    	while(i<j){ 
    		do{ 
    			i++;
    		}while(ans[i]<x);//当ans[i]>x退出循环应该放到x的右边
    	    do{ 
    	    	j--;
    		}while(ans[j]>x);//当ans[j]<x退出循环应该放到x的左边
    		if(i<j)
    		swap(ans[i],ans[j]);//当i<j把两个数交换
    
    		quicksort(ans,l,j);//递归
    		quicksort(ans,j+1,r);	
    }

int main()
    { 
    	  int n;
    	  cin>>n;
    	for(int i=0;i<n;i++){ 
    		cin>>ans[i];
    		
    	}
    	quicksort(ans,0,n-1);
    	for(int i=0;i<n;i++){ 
    		cout<<ans[i]<<" ";
    	}
    	return 0; 
     }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关【排序】快速排序

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

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

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

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

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

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

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

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

相关排序——快速排序

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

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

相关快速排序

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

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

相关快速排序

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

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

相关快速排序

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

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

相关快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分的记录都比另一部分小，然后再分别对这两个部分进行快速排序，最

心已赠人/ 2022年05月24日 01:42/ 0 赞/ 118 阅读

相关排序——快速排序

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

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