选择排序

含义

• 在数组内选择最小的数字排到最后面，与冒泡排序类似。

• 时间复杂度为$O(n^2)$

代码

int a[1145],n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		int t=i;
		for(int j=i+1;j<=n;j++){
			if(a[t]>a[j])t=j;
		}
		swap(a[i],a[t]);
  }

• 虽然与冒泡排序类似，但不稳定，建议无脑选冒泡排序。

——————————————————————————————————————————————————

插入排序

含义

• 顾名思义，插入排序就是指将数字插入到数组中。

• 它的时间复杂度为$O(n^2)$

代码

int a[1145],n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=2;i<=n;i++){
		for(int j=i-1;j>=1;j--){
			if(a[j]>a[j+1])swap(a[j],a[j+1]);
			else break;
		}
}

插入排序比较稳定，但还是不如冒泡排序。

——————————————————————————————————————————————————

冒泡排序

含义

• 字面意思，就是大的泡泡往上升，
• 时间复杂度为$O(n^2)$

代码

int a[1145],n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		bool f=1;
		for(int j=n;j>i;j--){
			if(a[j]<a[j-1]){
				swap(a[j],a[j-1]);
				f=0;
			}
		}
		if(f)break;
    }