快速排序

核心代码解析

1.函数定义：void quick_sort(int q[], int l, int r)
q 是要进行排序的数组。
l 和 r 分别是要排序的数组的起始和结束索引。
函数没有返回值，但会直接修改传入的数组。
2.如果 l 大于等于 r ，则直接返回，因为这意味着数组已经被排序了或者只包含一个元素。

3.选择数组的第一个元素 x=q[l] 作为基准元素。

4.使用两个指针 i 和 j 来搜索应该放在基准元素左侧和右侧的元素。开始时，i 指向 l 的前一个元素，j 指向 i 的下一个元素。

5.使用两个 while 循环来找到应该放在基准元素左侧和右侧的元素。
do i++; while(q[i]<x);：找到一个大于等于基准元素的元素。
do j++; while(q[j]>x);：找到一个小于等于基准元素的元素。
6.如果 i 小于 j ，则交换 q[i] 和 q[j] 。这样可以确保所有大于等于基准元素的元素都在其左侧，所有小于等于基准元素的元素都在其右侧。

7.对基准元素的左侧和右侧的子数组递归地调用快速排序。

8.最后，函数返回，不返回任何值。排序后的数组将留在原始数组中。

需要注意的是，这段代码没有包括一个名为 swap 的函数来交换两个元素的值。你需要自己实现这个函数，或者使用C语言中的库函数 swap()。

代码

#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=i+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]);
	
	
	return 0;
}