AcWing 785.快速排序

# 快速排序

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int l, int r){
	if(l >= r) return;

	int x = q[(l + r) / 2], 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(l, j);
	quick_sort(j + 1, r);
}
int main(){
	scanf("%d", &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;
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
//1e6 + 10的目的是为了防止越界
//因为数据范围大所以数组的话范围声明得N内

int q[N];
//声明数组


void quick_sort(int q[], int l, int r){
    if(l >= r) return;
    
    // int x = q[(l + r) / 2];
    //中间值取l或中间值都可以，这边取l
    
    
    //因为加强数据了 所以得取中间值
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    //这里为什么指向两侧呢，主要跟后面的写法有关系，因为边界性问题在考试期间不要浪费时间推，直接背就可以了
    
    while(i < j){
        //这里 do while 换成 while 的写法因为很多语言没有 do while 的写法
        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(){
    int n;
    scanf("%d", &n);
    //当输入数据比较多的时候。尽量选择一种比较快的输入方式
    //在C++里尽量用scanf来读入，不要用cin来读入
    
    
    
    //在java内用bufferread比scanner快10倍20倍
    
    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]);
    }
    return 0;
    
    
}