讨论详情 - Tom老师的信奥小站

C++
快速排序模版
mrhowe SU @ 2024-8-14 10:21:56

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;

int n,k;
int q[N];

int QuickSort(int q[], int l, int r,int k)
{
	if (l >= r) return q[l]; // 递归终止条件，一个或者0个数，不用排序 
	int x = q[(l + r) / 2];//选取分界线。这里选数组中间那个数
	int i = l-1, j = r+1; 
//划分成左右两个部分
	while (i < j)
	{
		// 这里写成do while 循环
		do i++; while (q[i] < x); 
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	if(j>=k){
		return QuickSort(q, l, j,k);
	}else return QuickSort(q, j+1, r,k);
	
	
}
int main()
{
	scanf("%d %d", &n,&k);
	for (int i = 0; i < n; i++) scanf("%d", &q[i]);
	cout<<QuickSort(q, 0, n-1,k);
	return 0;
}

mrhowe SU @ 2024-8-14 11:39:53

https://visualgo.net/zh/sorting

mrhowe SU @ 2024-8-14 11:39:23

插入排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[10]={10,11,3,22,22,15,9,26,9,19};
int main(){
	int i=0;
	while(i<9){
		i++;
		int t = i;
		while(a[t]<a[t-1]){
			int tmp;
			tmp = a[t];
			a[t] = a[t-1];
			a[t-1] = tmp;
			t--;
			if(t==0)break;
		}
	}
	for(int j=0;j<=9;j++){
		cout<<a[j]<<" ";
	}
	return 0;
}

选择排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[10]={10,11,3,22,22,15,9,26,9,19};
int main(){
	int t=0;
	while(t<9){
		int min_a=t;
		for(int i=t+1;i<=9;i++){
			if(a[i]<a[min_a]){
				min_a=i;
			}
		}
		swap(a[t],a[min_a]);
		t++;
	}
	for(int j=0;j<=9;j++){
		cout<<a[j]<<" ";
	}
	return 0;
}