考研算法第26天：快速排序【快排模版】

空が笑っています

已于 2023-06-27 16:20:05 修改

阅读量134

点赞数

分类专栏： C语言 c++ dvc++ 文章标签：大数据

于 2022-06-24 21:10:29 首次发布

本文链接： https://blog.csdn.net/qq_62556650/article/details/125451854

版权

c++ 同时被 3 个专栏收录

44 篇文章 0 订阅

订阅专栏

C语言

20 篇文章 0 订阅

订阅专栏

dvc++

17 篇文章 0 订阅

订阅专栏

题目：

我自己的快排：

就是过不了，好像这道题的测试样例有问题

(84条消息) 快速排序法（详解）_李小白~的博客-CSDN博客_快速排序

这个人讲的很详细

我的

#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
int a[100000];
void quick_sort(int *a,int l,int r){
	int i=l,j=r,value=a[i];
	if (l < r){
		while (i < j){
			while (i < j && a[j] >= value){
				j--;
			}
			if (i < j){
				a[i]=a[j];
				i++;
			}
			while (i < j && a[i] <= value){
				i++;
			}
			if (i < j){
				a[j]=a[i];
				j--;
			}
		}
		a[i] = value;
		quick_sort(a,l,i-1);
		quick_sort(a,i+1,r);
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for (int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
	quick_sort(a,1,n);
	for (int i=1; i<=n; i++){
		printf("%d ",a[i]);
	}
	return 0;
}

y总的：

#include <iostream>
using namespace std;
 
int a[100000];
 
void quick_sort(int l,int r){
    if(l>=r) return ;
    cout<<"I:"<<l<<"r:"<<r<<" "; 
    int mid = (l+r) >> 1;
	int i=l-1, j=r+1,value=a[mid];
	cout<<"value:"<<value<<" ";
	while(i<j){//这里是i<j而不是l<r因为这个while循环是将此时选定的value的左边和右边
	//大小区分开 所以是用代表这一次循环的i和j来进行循环
	do i++; while(a[i]<value&&i<j);
	do j--; while(a[j]>value&&i<j);	 
	 if(i<j) swap(a[i],a[j]);
	}
	
	for(int i=0;i<=r;i++){
		cout<<a[i]<<" ";
	} 
	cout<<"j:"<<j<<endl;
	quick_sort(l,j);
	quick_sort(j+1,r);
	
}
 
int main(){
	int n;
	cin>>n;
	cout<<"n:"<<n<<endl;
	for (int i=0; i<n; i++){
		scanf("%d",&a[i]);
	}
	quick_sort(0,n-1);
	for (int i=0; i<n; i++){
		printf("%d ",a[i]);
	}
	return 0;
}

更加详细的讲解

#include <iostream>

using namespace std;

const int N = 1000010;
int q[N];
void quick_sort(int l,int r){
    if(l>=r) return;
    int i = l-1,j = r+1;
    //y总的数据增强了，至于为啥这样就不会超时，
    //我也母鸡
    int rnd_idx = rand() % (r - l + 1) + l;
    swap(q[rnd_idx],q[l]);
    int x = q[l];
    while(i<j){
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        //这里注意需要多一个这样的判断，不然会多换一次
        //比如样例中的3 1 2 4 5
        //当换到左边区间换到1 2 的时候
        //i 还是满足 i<j 的
        //但是当再进入循环的时候，如果不对i<j的条件判断
        //再换一次，就会导致1 2 变成 2 1
        if(i<j)swap(q[i],q[j]);
    }
    //注意边界由于一般最终跳出来之后j=i-1,所以j做左区间的右边界最好
    quick_sort(l,j);
    quick_sort(j+1,r);
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    quick_sort(0,n-1);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}