问题标题: C++基** 1.1 简易快排函数代码 与其他排序代码

大家都知道，在编程中有很多排序，它们有不同的效率与复杂度，下面几种排序代码仅供参考：

1.选择排序

#include<iostream>
#include<cstdio>
#define MAXN 10005
using namespace std;
int a[MAXN],n;
void xz_sort(int l,int r){
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(a[j]<a[i])
				swap(a[i],a[j]);
		
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	xz_sort(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

选择排序的时间复杂度为O(n^2)如果n达到10^5就会超时，但它是稳定的排序

2.冒泡排序

#include<iostream>
#include<cstdio>
#define MAXN 10005
using namespace std;
int a[MAXN],n;
void mp_sort(int l,int r){
	for(int i=1;i<n;i++)
		for(int j=1;j<=n-i;j++)
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
	return ;
} 
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	mp_sort(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

冒泡排序的时间复杂度为O(n^2)如果n达到10^5就会超时，但它是稳定的排序

3.快速排序

#include<iostream>
using namespace std;
int a[10000005],n;
void qsort(int l,int r){
	int i=l,j=r;
	int mid=a[(i+j)/2];
	do{
		while(a[i]<mid)i++;
		while(a[j]>mid)j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}while(i<=j);
	if(l<j)qsort(l,j);
	if(i<r)qsort(i,r);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	qsort(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	return 0;
}

快速排序的时间复杂度为O(nlogn)它是不稳定的排序

同时，还有希尔排序、基数排序、堆排序等，初学暂时用不到

蒋宇韩在2022-10-07 20:44:00追加了内容

sort函数是对qsort的优化

蒋宇韩在2022-10-09 18:38:33追加了内容

@包思远 

确实，选择排序是不稳定的排序，我错了

but

qsort谁说我是百度？

蒋宇韩在2022-10-09 18:40:17追加了内容

@汪宇航

你见过哪个初学者上来学堆排？你吗？

蒋宇韩在2022-10-09 18:42:32追加了内容

qort和sort并不是完全一样

sort还包含了堆排，插入排序等，算是优化

蒋宇韩在2022-10-09 20:40:20追加了内容

https://blog.csdn.net/qq_37112826/article/details/112094420

自己看

蒋宇韩在2022-10-10 07:40:01追加了内容

@薛乘志 你牛* 但DL你是初学吗？